Minds and Machines 17 (2):217-231 (2007)
AbstractWhat are the limits of physical computation? In his ‘Church’s Thesis and Principles for Mechanisms’, Turing’s student Robin Gandy proved that any machine satisfying four idealised physical ‘principles’ is equivalent to some Turing machine. Gandy’s four principles in effect define a class of computing machines (‘Gandy machines’). Our question is: What is the relationship of this class to the class of all (ideal) physical computing machines? Gandy himself suggests that the relationship is identity. We do not share this view. We will point to interesting examples of (ideal) physical machines that fall outside the class of Gandy machines and compute functions that are not Turing-machine computable.
Added to PP
Historical graph of downloads
References found in this work
Shadows of the Mind: A Search for the Missing Science of Consciousness.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.
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.
Significance of Models of Computation, From Turing Model to Natural Computation.Gordana Dodig-Crnkovic - 2011 - Minds and Machines 21 (2):301-322.
Do Accelerating Turing Machines Compute the Uncomputable?B. Jack Copeland & Oron Shagrir - 2011 - Minds and Machines 21 (2):221-239.
The Dependence of Computability on Numerical Notations.Ethan Brauer - 2020 - Synthese 198 (11):10485-10511.
Practical Intractability: A Critique of the Hypercomputation Movement. [REVIEW]Aran Nayebi - 2014 - Minds and Machines 24 (3):275-305.
Similar books and articles
Physical Hypercomputation and the Church–Turing Thesis.Oron Shagrir & Itamar Pitowsky - 2003 - Minds and Machines 13 (1):87-101.
Reflections on Gödel's and Gandy's Reflections on Turing's Thesis.David Israel - 2002 - Minds and Machines 12 (2):181-201.
The Broad Conception of Computation.Jack Copeland - 1997 - American Behavioral Scientist 40 (6):690-716.
Quantum Speed-Up of Computations.Itamar Pitowsky - 2002 - Proceedings of the Philosophy of Science Association 2002 (3):S168-S177.