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.

## Recent comments

18 weeks 5 days ago

23 weeks 4 hours ago

24 weeks 4 days ago

24 weeks 4 days ago

27 weeks 2 days ago

31 weeks 6 days ago

31 weeks 6 days ago

32 weeks 2 days ago

32 weeks 2 days ago

35 weeks 1 day ago