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||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Dina Goldin & Peter Wegner (2008). The Interactive Nature of Computing: Refuting the Strong Church–Turing Thesis. [REVIEW] Minds and Machines 18 (1):17-38.
Mike Stannett (2003). Computation and Hypercomputation. Minds and Machines 13 (1):115-153.
Itamar Pitowsky (2003). Physical Hypercomputation and the Church–Turing Thesis. Minds and Machines 13 (1):87-101.
Oron Shagrir & Itamar Pitowsky (2003). Physical Hypercomputation and the Church–Turing Thesis. Minds and Machines 13 (1):87-101.
Saul A. Kripke (2013). The Church-Turing ‘Thesis’ as a Special Corollary of Gödel’s Completeness Theorem. In B. J. Copeland, C. Posy & O. Shagrir (eds.), Computability: Turing, Gödel, 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.
Added to index2009-01-28
Total downloads44 ( #29,783 of 722,826 )
Recent downloads (6 months)1 ( #60,541 of 722,826 )
How can I increase my downloads?