Hypercomputation and the physical church-Turing thesis
British Journal for the Philosophy of Science 54 (2):181-223 (2003)
| Abstract | A version of the Church-Turing Thesis states that every effectively realizable physical system can be defined by Turing Machines (‘Thesis P’); in this formulation the Thesis appears an empirical, more than a logico-mathematical, proposition. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. These models depend on infinite computation, explicitly or implicitly, and appear physically implausible; moreover, even if infinite computation were realizable, the Halting Problem would not be affected. Therefore, Thesis P is not essentially different from the standard Church-Turing Thesis. 1 Introduction 2 Computability and incomputability 3 The physical interpretation of the Church-Turing Thesis 4 Supertasks and infinite computation 5 Computation on non-well-founded domains 6 Analog computation 7 Quantum computation 8 Retrocausal computation 9 Conclusions. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,705 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesDina Goldin & Peter Wegner (2008). The Interactive Nature of Computing: Refuting the Strong Church–Turing Thesis. Minds and Machines 18 (1).
Mike Stannett (2003). Computation and Hypercomputation. Minds and Machines 13 (1):115-153.
Oron Shagrir & Itamar Pitowsky (2003). Physical Hypercomputation and the Church–Turing Thesis. Minds and Machines 13 (1):87-101.
Saul A. Kripke (forthcoming). Another Approach: The Church-Turing ‘Thesis’ as a Special Corollary of Gödel’s Completeness Theorem. In B. J. Copeland, C. Posy & O. Shagrir (eds.), Computability: Gödel, Turing, Church, and beyond. MIT Press.
B. Jack Copeland (2008). The Church-Turing Thesis. In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
Itamar Pitowsky (2002). Quantum Speed-Up of Computations. Proceedings of the Philosophy of Science Association 2002 (3):S168-S177.
Tim Button (2009). Sad Computers and Two Versions of the Church–Turing Thesis. British Journal for the Philosophy of Science 60 (4):765-792.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads42 ( #27,087 of 549,196 )Recent downloads (6 months)1 ( #63,397 of 549,196 )How can I increase my downloads? |
My notes
Discussion
