Hypercomputation and the Physical Church‐Turing Thesis


Authors
Abstract
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
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


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

References found in this work BETA

The Emperor's New Mind.Roger Penrose - 1989 - Oxford University Press.
Shadows of the Mind.Roger Penrose - 1994 - Oxford University Press.
On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.

View all 45 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 14 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.B. Jack Copeland & Diane Proudfoot - 2000 - Journal of Logic, Language and Information 9 (4):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.

Analytics

Added to PP index
2009-01-28

Total views
114 ( #65,608 of 2,250,064 )

Recent downloads (6 months)
14 ( #64,480 of 2,250,064 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature