Computability and recursion

Bulletin of Symbolic Logic 2 (3):284-321 (1996)
Abstract
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)
DOI 10.2307/420992
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 26,188
Through your library
References found in this work BETA
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.
Finite Combinatory Processes-Formulation.Emil L. Post - 1936 - Journal of Symbolic Logic 1 (3):103-105.
Computability and Λ-Definability.A. M. Turing - 1937 - Journal of Symbolic Logic 2 (4):153-163.

View all 6 references / Add more references

Citations of this work BETA
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.

View all 11 citations / Add more citations

Similar books and articles

Monthly downloads

Added to index

2009-01-28

Total downloads

31 ( #162,023 of 2,153,858 )

Recent downloads (6 months)

1 ( #398,274 of 2,153,858 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums