A version of the Church-Turing Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. This yields that the realization of hypercomputing devices is implausible, and that Thesis P is not essentially different from the standard Church-Turing Thesis.
Keywords Church-Turing Thesis  Hypercomputation  Supertasks  Incomputability  Non-standard computation
Categories (categorize this paper)
DOI 10.1093/bjps/54.2.181
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 59,759
Through your library

References found in this work BETA

The Emperor’s New Mind.Roger Penrose - 1989 - Oxford University Press.
On Computable Numbers, with an Application to the N Tscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
An Unsolvable Problem of Elementary Number Theory.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (2):73-74.

View all 46 references / Add more references

Citations of this work BETA

Computing Mechanisms.Gualtiero Piccinini - 2007 - Philosophy of Science 74 (4):501-526.
The Physical Church–Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.

View all 16 citations / Add more citations

Similar books and articles

SAD Computers and Two Versions of the Church–Turing Thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
Computation and Hypercomputation.Mike Stannett - 2003 - Minds and Machines 13 (1):115-153.
Hypercomputation.B. Jack Copeland - 2002 - Minds and Machines 12 (4):461-502.
What Turing Did After He Invented the Universal Turing Machine.Diane Proudfoot & Jack Copeland - 2000 - Journal of Logic, Language and Information 9:491-509.
Quantum Speed-Up of Computations.Itamar Pitowsky - 2002 - Proceedings of the Philosophy of Science Association 2002 (3):S168-S177.
The Church-Turing Thesis.B. Jack Copeland - 2008 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
A Brief Critique of Pure Hypercomputation.Paolo Cotogno - 2009 - Minds and Machines 19 (3):391-405.
Buttresses of the Turing Barrier.Paolo Cotogno - 2015 - Acta Analytica 30 (3):275-282.
Hypercomputation: Computing More Than the Turing Machine.Toby Ord - 2002 - Dissertation, University of Melbourne


Added to PP index

Total views
131 ( #77,617 of 2,432,623 )

Recent downloads (6 months)
4 ( #170,117 of 2,432,623 )

How can I increase my downloads?


My notes