David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Bulletin of Symbolic Logic 2 (3):284-321 (1996)
We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. After a careful historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving the intensional differences between the concepts of "computability" and "recursion." Specifically we recommend that: the term "recursive" should no longer carry the additional meaning of "computable" or "decidable;" functions defined using Turing machines, register machines, or their variants should be called "computable" rather than "recursive;" we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be "Computability Theory" or simply Computability rather than "Recursive Function Theory."
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Nir Fresco (2011). Concrete Digital Computation: What Does It Take for a Physical System to Compute? [REVIEW] Journal of Logic, Language and Information 20 (4):513-537.
Aran Nayebi (2014). Practical Intractability: A Critique of the Hypercomputation Movement. [REVIEW] Minds and Machines 24 (3):275-305.
Marcus Tomalin (2011). Syntactic Structures and Recursive Devices: A Legacy of Imprecision. [REVIEW] Journal of Logic, Language and Information 20 (3):297-315.
Leo Harrington & Robert I. Soare (1998). Definable Properties of the Computably Enumerable Sets. Annals of Pure and Applied Logic 94 (1-3):97-125.
Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel (1998). Difference Sets and Computability Theory. Annals of Pure and Applied Logic 93 (1-3):63-72.
Similar books and articles
Piergiorgio Odifreddi (1989). Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers. Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co..
Nigel Cutland (1980). Computability, an Introduction to Recursive Function Theory. Cambridge University Press.
Stewart Shapiro (1983). Remarks on the Development of Computability. History and Philosophy of Logic 4 (1-2):203-220.
Michael Rescorla (2007). Church's Thesis and the Conceptual Analysis of Computability. Notre Dame Journal of Formal Logic 48 (2):253-280.
Eli Dresner (2008). Turing-, Human- and Physical Computability: An Unasked Question. [REVIEW] Minds and Machines 18 (3):349-355.
Guido Gherardi (2011). Alan Turing and the Foundations of Computable Analysis. Bulletin of Symbolic Logic 17 (3):394-430.
S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.) (1996). Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press.
Added to index2009-01-28
Total downloads19 ( #145,074 of 1,725,575 )
Recent downloads (6 months)3 ( #211,098 of 1,725,575 )
How can I increase my downloads?