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

10 hours 58 min ago

11 hours 49 min ago

12 hours 30 sec ago

13 hours 51 min ago

16 hours 31 min ago

17 hours 53 min ago

17 hours 59 min ago

18 hours 7 min ago

18 hours 39 min ago

1 day 4 hours ago