Minds and Machines 13 (1):87-101 (2003)
AbstractWe describe a possible physical device that computes a function that cannot be computed by a Turing machine. The device is physical in the sense that it is compatible with General Relativity. We discuss some objections, focusing on those which deny that the device is either a computer or computes a function that is not Turing computable. Finally, we argue that the existence of the device does not refute the Church–Turing thesis, but nevertheless may be a counterexample to Gandy's thesis.
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.
Quantum speed-up of computations.Itamar Pitowsky - 2002 - Proceedings of the Philosophy of Science Association 2002 (3):S168-S177.
Turing-, human- and physical computability: An unasked question. [REVIEW]Eli Dresner - 2008 - Minds and Machines 18 (3):349-355.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
The Church-Turing Thesis.B. Jack Copeland - 2008 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
Physical Computation: How General are Gandy’s Principles for Mechanisms?B. Jack Copeland & Oron Shagrir - 2007 - Minds and Machines 17 (2):217-231.
Added to PP
Historical graph of downloads
Citations of this work
The Physical Church–Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.
Hypercomputation and the Physical Church‐Turing Thesis.Paolo Cotogno - 2003 - British Journal for the Philosophy of Science 54 (2):181-223.
References found in this work
On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Shadows of the Mind: A Search for the Missing Science of Consciousness.Roger Penrose - 1994 - Oxford University Press.
The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions.Martin Davis (ed.) - 1965 - Hewlett, NY, USA: Dover Publication.
Systems of Logic Based on Ordinals.Alan Mathison Turing - 1939 - London: Printed by C.F. Hodgson & Son.