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
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 46,461
Through your library

References found in this work BETA

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.
Computability and Logic.George S. Boolos, John P. Burgess & Richard C. Jeffrey - 2003 - Bulletin of Symbolic Logic 9 (4):520-521.
Mathematical Thought From Ancient to Modern Times.M. Kline - 1978 - British Journal for the Philosophy of Science 29 (1):68-87.

View all 42 references / Add more references

Citations of this work BETA

The Representational Foundations of Computation.Michael Rescorla - 2015 - Philosophia Mathematica 23 (3):338-366.

View all 31 citations / Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
91 ( #95,700 of 2,286,456 )

Recent downloads (6 months)
40 ( #23,419 of 2,286,456 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature