Lambda the Ultimate

This paper seeks to explode the myth that Turing Machines (TM) are the universal model for all computation.

Church-Turing Thesis: Whenever there is an effective method (algorithm) for obtaining the values of a mathematical function, the function can be computed by a TM.

[...] The Church-Turing thesis has since been reinterpreted to imply that Turing Machines model all computations, rather than just functions. This claim, which we call the Strong Church-Turing Thesis, is part of the mainstream theory of computation. In particular, it can be found in today's popular undergraduate theory textbooks:

Strong Church-Turing Thesis: A TM can do (compute) anything that a computer can do.

It is a myth that the original Church-Turing thesis is equivalent to this interpretation of it; Turing himself would have denied it. [...] In fact, the Strong Church-Turing Thesis is incorrect - the function-based behaviour of algorithms does not capture all forms of computation. For example, as explained in [Weg97], interactive protocols are not algorithmic.

[...] The reasons for the widespread acceptance of what we call the "Turing Thesis Myth" can be traced to the establishment of computer science as a separate discipline in the 1960's. To understand these reasons better, we can identify three distinct claims that make up the myth, and examine them individually:

• Claim 1. All computable problems are function-based.
  • Reason: Adoption of mathematical principles for the fundamental notions of computation, identifying computability with the computation of functions, as well as with TMs.
• Claim 2. All computable problems can be described by an algorithm.
  • Reason: Adoption of algorithms as the central and complete concept of computer science.
• Claim 3. Algorithms are what computers do.
  • Reason: Broadening the concept of an algorithm to make it more practical.

Each claim is then explained in detail, and refuted, along with a few other corroborating claims. The paper concludes with an extension to TMs to model interactive computation.