I was reading "Why Only Us" by Chomsky and Berwick, and it said:

If one subscribes to the Church-Turing thesis along with the assumption that the brain is finite, then there is no way out: we require some notion of recursion to adequately describe such phenomena.

I find this sentence confusing. What does the Church-Turing thesis have to do with recursion and the human brain? If anything, it seems obviously false to me because the Church-Turing thesis talks about computable things that require a Turing Machine, which in turn obviously requires an infinite tape. The brain obviously doesn't have this since the brain is finite, unless we somehow assume the brain can always "get a new piece of paper to write on". But even if that was resolved, what does recursion have to do with this, and how is any of this related to language?

  • $\begingroup$ Can you give us more context? It's hard for me to understand what point that might be making from just the quote you list. $\endgroup$
    – D.W.
    May 14, 2017 at 1:39
  • $\begingroup$ It's a very long passage - putting all of the relevant information into a single question would be rather unwieldy. I assume he's really asking someone who is familiar with the source work to comment. $\endgroup$
    – Ben I.
    May 14, 2017 at 1:43
  • $\begingroup$ @D.W. the book is about why (complex) language evolved mainly on humans and not other species. In the beginning of the book it seems that they try to argue that human language is intrinsically hierarchical/compositional/recursive. Some how the believing the Church-Turning thesis and accepting that the brain is finite should lead me to believe that its necessary to have a complete theory of language, it must in itself be recursive. Thats just my guess. Basically IF Church-Turning & Brain finite THEN recursion. Not sure I buy it or understand their reasoning...thats what Im trying to understand $\endgroup$ May 14, 2017 at 1:43
  • 1
    $\begingroup$ I interpret "recursion" as used in the formal languages context "... Recursive languages are also called decidable....". In other words if CTT is true and the brain is finite, then there is no undecidable stuff; and there is a Turing machine that can "decide" (or simulate) deterministically every aspect of the brain (thoughts, dreams, responses to inputs, ..) $\endgroup$
    – Vor
    May 17, 2017 at 12:08
  • 1
    $\begingroup$ Note that Chomskyan linguistics is already quite old and many linguists nowadays don't agree with his generative grammar approach at all. See symbolist vs. connectionist debate in cognitive science for some analogies. Chomsky's ideas were actually very helpful for formal language theories, i.e. PL/compiler-related things, but it makes very little sense when characterizing real human languages. Real breakthroughs in NLP are only made with modern deep learning approaches instead of traditional binary logic approaches as well. $\endgroup$
    – xji
    May 19, 2017 at 17:20

1 Answer 1


This was a fun little rabbit-hole to jump into! My understanding is not that dissimilar from what you wrote in your comment:

"Basically IF Church-Turning & Brain finite THEN recursion."

But you forgot to add "and if there is arbitrarily deep layering of semantic meaning". So, really we would have:

If arbitrarily deep semantic layering AND the Church-Turing Thesis AND a finite brain, THEN recursion.

Now let's see if I can unpack that a little for you.

The authors are arguing that the components of sentences are placed into semantic layers that can group words rather differently than strict word-ordering would suggest, and furthermore, that these layers are effectively unlimited. Consider this sentence:

Mary and John went to the new movie (which was excellent) with Sam.

Mary, John, and Sam are at one semantic layer, the new movie is at a second, and the fact that the movie was excellent is at yet a third layer.

Mary and John went to the new movie, (which, as you expected, was excellent) with Sam.

We've now added a fourth semantic layer. And, I hope it is obvious that we could keep going! The sentence would become convoluted and hard to follow, but we could keep adding semantic layers as many times as we wish.

There is a second idea here as well. It is interesting that Mary, John, and Sam are at the same semantic layer, even though they are far apart in the sentence. This is evidence that there really is some kind of semantic layering, and not merely word proximity at play. We read "Mary and John", delve down into a new layer, and eventually return back to this first layer in order to add "with Sam". I mention this because it is already suggestive of recursion!

I understand your objection about having a finite amount of brain, and it is a very good counter-argument to the idea that we can follow arbitrarily deep semantic layers, but it is not an objection to the idea that human language is structured to be able to create them, which is really what the authors are arguing.

If you accept that language is structured in such a way as to permit this arbitrarily deep layering, then you are doing something very similar to a Turing Machine, which can represent any computable function using a finite number of states.

The Church-Turing thesis involves the notion that all of these representations are, somehow, recursive. This makes sense if you consider that all three of the systems involved (Godel, Turing, and Church) can do this same trick of going arbitrarily deep using a finite number of rules at the start. There must be some mechanism that allows arbitrary depth, which means that we must be able to repeat rules or states, which means recursion.

We are very close to having finished here. If arbitrarily deep semantic layering AND the Church-Turing Thesis AND a finite brain, THEN recursion.

We only are left with the finite brain. But of course, if the brain were infinite, then we would have no need for recursion. We could represent every semantic layer in a new region of the brain, and keep doing this forever.

  • $\begingroup$ but if the brain is not "infinite" then we can't simulate a Turing Machine since we need infinite tape, no? Or am I missing something? $\endgroup$ May 14, 2017 at 2:32
  • 1
    $\begingroup$ You're getting stuck at the memory side, but they are really referring to the state side of the TM. The only way to have arbitrarily deep layering with a finite number of states is with some kind of recursive capability. The lack of infinite tape is why we can't follow our language constructs infinitely far, but the language constructs themselves still allow for arbitrary depth of semantic layers, even if there is a limit to how many of them we can process. $\endgroup$
    – Ben I.
    May 14, 2017 at 3:14
  • 1
    $\begingroup$ If you're still confused, I'm happy to answer more questions $\endgroup$
    – Ben I.
    May 15, 2017 at 21:12
  • $\begingroup$ I will give you more question, but I have not found the time to sit down and think about it properly. I will as soon as I find the time! $\endgroup$ May 16, 2017 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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