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

Abstract
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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2009.01.008
Options
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: 53,688
Through your library

References found in this work BETA

Computing Machinery and Intelligence.Alan M. Turing - 1950 - Mind 59 (October):433-60.
Computability and Recursion.Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (3):284-321.
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 25 references / Add more references

Citations of this work BETA

Why Think That the Brain is Not a Computer?Marcin Miłkowski - 2016 - APA Newsletter on Philosophy and Computers 16 (2):22-28.
Semiotic Systems, Computers, and the Mind: How Cognition Could Be Computing.William J. Rapaport - 2012 - International Journal of Signs and Semiotic Systems 2 (1):32-71.
The Philosophy of Computer Science.Raymond Turner - 2013 - Stanford Encyclopedia of Philosophy.
Synchronous Online Philosophy Courses: An Experiment in Progress.Fritz McDonald - 2018 - APA Newsletter on Philosophy and Computers 18 (1):37-40.

View all 12 citations / Add more citations

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.

Analytics

Added to PP index
2013-12-22

Total views
22 ( #453,196 of 2,349,657 )

Recent downloads (6 months)
4 ( #187,247 of 2,349,657 )

How can I increase my downloads?

Downloads

My notes