0
$\begingroup$

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?

$\endgroup$
5
  • 8
    $\begingroup$ What does it mean for English to compute a function? You can't call something Turing-complete if it's not computing anything. $\endgroup$ Jul 22 '20 at 1:33
  • 1
    $\begingroup$ Re: "English is Turing complete since you can talk someone through building a Turing machine", consider The Treachery of Images. $\endgroup$ Jul 22 '20 at 1:41
  • $\begingroup$ What do it mean for Solidity to compute a function? Is Solidity not Turing-complete? $\endgroup$ Jul 22 '20 at 2:33
  • $\begingroup$ If that drawn pipe isn't a pipe, then the written "This is not a pipe" isn't "this is not a pipe" either. I prefer this: en.wikipedia.org/wiki/An_Oak_Tree $\endgroup$ Jul 22 '20 at 2:36
  • 1
    $\begingroup$ Assuming you are referring to Solidity the smart contracts programming language, it looks to me like it is technically not Turing complete but rather a linear bounded automaton because there are fixed limits on stack size etc. However, it does have computational semantics: you can give it inputs and define what the outputs are supposed to be, through a series of reduction operations. $\endgroup$ Jul 22 '20 at 4:04
7
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ @Vor Having a hard time with the semantics of "give me the collection of sets that do not contain themselves". $\endgroup$ Jul 23 '20 at 22:10
  • 2
    $\begingroup$ @Vor: You are confusing the language with its meaning. For a language to be a "programming language" in any sense of the word, the language must be assigned something that resembles a notion of computation. I am not saying this isn't possible, I am saying that in itself English has no such meaning. Perhaps if you shift attention to humans, you can get a model of computation, but then it's going to be about brains and minds, not about English. $\endgroup$ Jul 24 '20 at 6:48
  • 1
    $\begingroup$ For instance, suppose I define the operational semantics of English as "The operational meaning of $P$ are the actions performed by a human upon hearing $P$", and let's pretend all humans would act the same way upon hearing $P$. This is a bit like saying that the meaning of a program on a tape is whatever the Universal Turing machine does when given the tape – which is a sort of operational semantics, but it presumes an operational semantics of the Universal Turing machine. Likewise, my attempted definition does so for humans, so it's basically a reduction to a different problem. $\endgroup$ Jul 24 '20 at 6:51
  • 3
    $\begingroup$ What gives the meaning to "Put a stone in the box"? Let me demonstrate. If you think English as a syntactic entity has a meaning in itself, then surely you'd think the same about Slovene. Please execute "Vzemi kamen iz škatle". No? So then the meaning of the English language is intricately related to the human understanding of it, and what you are really asking is whether "humans are Turing complete" (as much as that can make sense). It's easier to argue that a human is like a computer (look up the old definition of "computer"...) that "English is a programming language". $\endgroup$ Jul 24 '20 at 7:43
  • 1
    $\begingroup$ English is a programming language by proxy, indirectly, i.e., as intepreted by humans. So the focus should be on humans. But I am repeating myself. If you're going to say we could use English to program computers, yes we could, but before we did that the computers would require us to encode an operational semantics for English, which is currently lacking from the OP's question. In the above comment I proposed one, but I personally think the entire endavor is a bit silly and pointless. $\endgroup$ Jul 24 '20 at 7:46
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Not sure what is the primary objection to this answer, but I would love to know! If anyone wants to comment (downvoter or not). $\endgroup$
    – 6005
    Jul 26 '20 at 19:29
  • $\begingroup$ The Berry paradox also exists in Python: It's easy to write a Python function that appears to test all programs of at most n lines of code and checks for the largest <class 'int'> and then adds one. But neither the English sentence nor the Python are valid descriptions because they both require solving the halting problem. $\endgroup$ Sep 6 at 18:26
0
$\begingroup$

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 :-)

$\endgroup$
2
  • $\begingroup$ Is XML Turing-complete? You could give some XML constructs certain programming meaning, but saying that XML is a programming language is at least confusing. $\endgroup$ Jul 27 '20 at 7:46
  • $\begingroup$ @DmitriUrbanowicz: in order to say that a language is Turing complete, you must consider it with the model of computation in which it is used. Clearly English+human behavior forms a "natural" pair language+model of computation (you write some English sentences and humans act according to them). Clearly with many "approximations" (I don't say that it is rigorous), but nevertheless if you consider a C program Turing complete when executed in a computer (relaxing the infinite memory requirement) then it seems natural (to me) to consider English Turing complete when "interpreted" by humans. $\endgroup$
    – Vor
    Jul 27 '20 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.