Minds and Machines 21 (2):221-239 (2011)

Oron Shagrir
Hebrew University of Jerusalem
Accelerating Turing machines have attracted much attention in the last decade or so. They have been described as “the work-horse of hypercomputation”. But do they really compute beyond the “Turing limit”—e.g., compute the halting function? We argue that the answer depends on what you mean by an accelerating Turing machine, on what you mean by computation, and even on what you mean by a Turing machine. We show first that in the current literature the term “accelerating Turing machine” is used to refer to two very different species of accelerating machine, which we call end-stage-in and end-stage-out machines, respectively. We argue that end-stage-in accelerating machines are not Turing machines at all. We then present two differing conceptions of computation, the internal and the external, and introduce the notion of an epistemic embedding of a computation. We argue that no accelerating Turing machine computes the halting function in the internal sense. Finally, we distinguish between two very different conceptions of the Turing machine, the purist conception and the realist conception; and we argue that Turing himself was no subscriber to the purist conception. We conclude that under the realist conception, but not under the purist conception, an accelerating Turing machine is able to compute the halting function in the external sense. We adopt a relatively informal approach throughout, since we take the key issues to be philosophical rather than mathematical.
Keywords ATM paradox   Accelerating Turing machine   Epistemic embedding   External and internal computation   Halting problem   Hypercomputation   Ontology of computing   Supertask   Thompson lamp paradox   Turing-machine purism   Turing-machine realism
Categories (categorize this paper)
DOI 10.1007/s11023-011-9238-y
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: 69,078
Through your library

References found in this work BETA

Word and Object.Willard Van Orman Quine - 1960 - Cambridge, MA, USA: MIT Press.
Computing Machinery and Intelligence.Alan M. Turing - 1950 - Mind 59 (October):433-60.
Word and Object.Willard Van Orman Quine - 1960 - Les Etudes Philosophiques 17 (2):278-279.
On Computable Numbers, with an Application to the N Tscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.

View all 54 references / Add more references

Citations of this work BETA

The Philosophy of Computer Science.Raymond Turner - 2013 - Stanford Encyclopedia of Philosophy.
Why Do We Need a Theory of Implementation?Andre Curtis-Trudel - forthcoming - British Journal for the Philosophy of Science.
Implementation as Resemblance.André Curtis-Trudel - 2021 - Philosophy of Science 88 (5):1021-1032.

View all 9 citations / Add more citations

Similar books and articles

Accelerating Turing Machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
The Broad Conception of Computation.Jack Copeland - 1997 - American Behavioral Scientist 40 (6):690-716.
Two Dogmas of Computationalism.Oron Shagrir - 1997 - Minds and Machines 7 (3):321-44.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
Supermachines and Superminds.Eric Steinhart - 2003 - Minds and Machines 13 (1):155-186.
What Turing Did After He Invented the Universal Turing Machine.Diane Proudfoot & Jack Copeland - 2000 - Journal of Logic, Language and Information 9:491-509.
Hypercomputation: Computing More Than the Turing Machine.Toby Ord - 2002 - Dissertation, University of Melbourne
Infinite Time Turing Machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.
WHAT IS. . . A Halting Probability?Cristian S. Calude - 2010 - Notices of the AMS 57:236-237.


Added to PP index

Total views
139 ( #82,950 of 2,498,795 )

Recent downloads (6 months)
6 ( #118,323 of 2,498,795 )

How can I increase my downloads?


My notes