Turing oracle machines, online computing, and three displacements in computability theory

Annals of Pure and Applied Logic 160 (3):368-399 (2009)
  Copy   BIBTEX


We begin with the history of the discovery of computability in the 1930’s, the roles of Gödel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines . To whom did Gödel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine and Post’s development of it in [1944, §11], [1948], and finally Kleene-Post [1954] into its present form. A number of topics arose from Turing functionals including continuous functionals on Cantor space and online computations. Almost all the results in theoretical computability use relative reducibility and o-machines rather than a-machines and most computing processes in the real world are potentially online or interactive. Therefore, we argue that Turing o-machines, relative computability, and online computing are the most important concepts in the subject, more so than Turing a-machines and standard computable functions since they are special cases of the former and are presented first only for pedagogical clarity to beginning students. At the end in §10–§13 we consider three displacements in computability theory, and the historical reasons they occurred. Several brief conclusions are drawn in §14



    Upload a copy of this work     Papers currently archived: 74,662

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Hypercomputation.B. Jack Copeland - 2002 - Minds and Machines 12 (4):461-502.
Accelerating Turing Machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
Computability and Recursion.Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (3):284-321.
Infinite Time Turing Machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.
Infinite Time Turing Machines.Joel David Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.
Computable Diagonalizations and Turing’s Cardinality Paradox.Dale Jacquette - 2014 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 45 (2):239-262.


Added to PP

29 (#399,980)

6 months
1 (#419,921)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Computing Machinery and Intelligence.Alan M. Turing - 1950 - Mind 59 (October):433-60.
On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
A Note on the Entscheidungsproblem.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (1):40-41.
On Notation for Ordinal Numbers.S. C. Kleene - 1938 - Journal of Symbolic Logic 3 (4):150-155.

View all 30 references / Add more references