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
2 hours 13 min ago
13 hours 11 min ago
19 hours 20 sec ago
19 hours 20 min ago
19 hours 50 min ago
20 hours 35 min ago
20 hours 59 min ago
21 hours 27 min ago
23 hours 1 min ago
23 hours 25 min ago