Computability and recursion

Bulletin of Symbolic Logic 2 (3):284-321 (1996)
  Copy   BIBTEX


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."



    Upload a copy of this work     Papers currently archived: 94,659

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Minimal weak truth table degrees and computably enumerable Turing degrees.R. G. Downey - 2020 - Providence, RI: American Mathematical Society. Edited by Keng Meng Ng & Reed Solomon.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
Computability & unsolvability.Martin Davis - 1958 - New York: Dover Publications.
Computation and hypercomputation.Mike Stannett - 2003 - Minds and Machines 13 (1):115-153.
Remarks on the development of computability.Stewart Shapiro - 1983 - History and Philosophy of Logic 4 (1-2):203-220.


Added to PP

201 (#103,461)

6 months
30 (#127,624)

Historical graph of downloads
How can I increase my downloads?

References found in this work

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.
Computing Machinery and Intelligence.Alan M. Turing - 2003 - In John Heil (ed.), Philosophy of Mind: A Guide and Anthology. New York: Oxford University Press.
Grundzüge der theoretischen Logik.D. Hilbert & W. Ackermann - 1928 - Annalen der Philosophie Und Philosophischen Kritik 7:157-157.
A note on the entscheidungsproblem.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (1):40-41.

View all 44 references / Add more references