TransWikia.com

Is English Turing-complete?

Computer Science Asked on November 15, 2021

Is English Turing-complete?

Intuitively it makes sense that English is Turing complete, since you can talk someone through building a Turing machine. But I also think there might be some operators used in programming that aren’t used in person-to-person communication, at least in daily life.

Also, what level of English is required until it becomes Turing complete? For example: 1st grade? College level?

3 Answers

English is neither a language with a given operational semantics nor a model of computation of any other kind. Your question does not make sense.

Answered by Andrej Bauer on November 15, 2021

The problem with your question is that there are fundamental differences bewteen natural languages (such as English) and programming languages such as Java, Python, or Turing machines: natural languages are inherently ambiguous, while programming languages are inherently unambiguous. Because of this, as Andrej Bauer says, what it means for an English sentence to "compute" something can't be well defined in general.

For example, consider the following simple program (written in a Python-like pseudocode):

my_program(i):
    if i > 10:
        infinite_loop()
    else if i > 0:
        crash()
    else:
        print("Hello world!")

The thing to notice about this program (and all programs) is that there is only one possible semantics for the program. The program takes as input a natural number $i$ and its behavior is completely determined by what $i$ is. To be clear, the actual behavior may differ: if $i > 10$ then it runs forever, if $i in {1, 2, 3, ldots, 9}$ it crashes, and if $i le 0$ then it prints a string and terminates. But given a fixed value of the input $i$, the behavior is always the same; there is never any ambiguity about it. The compiler cannot simply choose to interpret your code differently than what you wrote, and say, crash when give input $i = 15$. In summary, programs unambiguously correspond to a unique set of possible behaviors.

In contrast, a natural language such as English if full of ambiguities that mean English sentences do not always correspond to a unique set of possible behaviors. A famous example of this is the Berry paradox, which is the following simple phrase:

The smallest positive integer not definable in under sixty letters.

This appears to be perfectly valid English; it makes sense. In fact, it appears to refer to an unambiguous integer. Yet, it actually does not. Because, suppose it referred to some integer $n$. Then $n$ is the smallest positive integer not definable in under sixty letters; but the above is a description of $n$ in 57 letters! So this is a contradiction. We can only conclude that, despite seeming to make sense, the above sentence does not actually refer unambiguously to a number. In other words, English is ambiguous.

The same problem, although less obviously paradoxical, happens all the time in everyday speaking; Wikipedia gives many examples, such as

I'm glad I'm a man, and so is Lola

which is perfectly valid English, but has not just two, but three different possible meanings.

Now returning to your question:

Is English Turing-complete?

There is a fundamental issue here. It does not even make sense to refer to English as Turing complete or not, because we do not know any way of associating English sentences unambiguously to possible behaviors (or to possible Turing machines). While your argument is perfectly reasonable:

Intuitively it makes sense that English is Turing complete since you can talk someone through building a Turing machine.

it falls apart, because although there are many ways of describing how to build a Turing machine, most of them will be ambiguous. So what do you define as a valid description? For example, is the following a valid description of the Turing machine?

The Turing machine with the smallest number of states that can't be described in 100 or fewer letters.

If it is not valid, then what is a valid description? If you manage to answer this, providing an unambiguous way to describe everything (such as, say, mathematical logic stated in English), then I claim that actually you are no longer speaking English! Instead, you have just invented a specialized programming language, a small subset of English for which you have defined the meaning of the words.

Answered by 6005 on November 15, 2021

Yes it's "Turing complete" ... and the only words needed are those that you can use to describe the behaviour of a Turing machine:

"if you're wearing a hat of color $x$ and find (or don't find) a stone in the box in front of you, then wear a new hat of color $x'$, put/remove a stone in/from the box and move to the next/previous box"

... it could be a child game :-)

Answered by Vor on November 15, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP