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

9 hours 26 min ago

9 hours 42 min ago

10 hours 34 min ago

11 hours 21 min ago

11 hours 49 min ago

12 hours 11 min ago

12 hours 29 min ago

13 hours 12 min ago

13 hours 33 min ago

13 hours 49 min ago