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)|
References found in this work BETA
Über eine bisher noch nicht benützte erweiterung Des finiten standpunktes.Von Kurt Gödel - 1958 - Dialectica 12 (3‐4):280-287.
Finite Combinatory Processes-Formulation.Emil L. Post - 1936 - Journal of Symbolic Logic 1 (3):103-105.
Citations of this work BETA
Practical Intractability: A Critique of the Hypercomputation Movement. [REVIEW]Aran Nayebi - 2014 - Minds and Machines 24 (3):275-305.
Syntactic Structures and Recursive Devices: A Legacy of Imprecision. [REVIEW]Marcus Tomalin - 2011 - Journal of Logic, Language and Information 20 (3):297-315.
Concrete Digital Computation: What Does It Take for a Physical System to Compute? [REVIEW]Nir Fresco - 2011 - Journal of Logic, Language and Information 20 (4):513-537.
The Representational Foundations of Computation.Michael Rescorla - 2015 - Philosophia Mathematica 23 (3):338-366.
Parsimony Hierarchies for Inductive Inference.Andris Ambainis, John Case, Sanjay Jain & Mandayam Suraj - 2004 - Journal of Symbolic Logic 69 (1):287-327.
Similar books and articles
Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers.Piergiorgio Odifreddi - 1989 - Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co..
Computability, Enumerability, Unsolvability: Directions in Recursion Theory.S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.) - 1996 - Cambridge University Press.
Alan Turing and the Foundations of Computable Analysis.Guido Gherardi - 2011 - Bulletin of Symbolic Logic 17 (3):394-430.
Turing-, Human- and Physical Computability: An Unasked Question. [REVIEW]Eli Dresner - 2008 - Minds and Machines 18 (3):349-355.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
Remarks on the Development of Computability.Stewart Shapiro - 1983 - History and Philosophy of Logic 4 (1-2):203-220.
Computability, an Introduction to Recursive Function Theory.Nigel Cutland - 1980 - Cambridge University Press.
Computability Theory: An Introduction to Recursion Theory.Herbert B. Enderton - 2011 - Academic Press.
Added to index2009-01-28
Total downloads31 ( #162,023 of 2,153,858 )
Recent downloads (6 months)1 ( #398,274 of 2,153,858 )
How can I increase my downloads?