The DOI matches its Crossref record; 66 of the 66 references it cites were found in a registry or an index.
Computability and Recursion
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.”
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
I.—COMPUTING MACHINERY AND INTELLIGENCE
TURING, A. M. (1950) · Mind · doi:10.1093/mind/lix.236.433 · Cited by 10,290
On computable numbers, with an application to the entscheidungsproblem
Turing, A. M. (1937) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-42.1.230 · Cited by 8,283
Computing Machinery and Intelligence (1950)
Turing, A. (2004) · The Essential Turing · doi:10.1093/oso/9780198250791.003.0017 · Cited by 6,118
Introduction to Metamathematics
Rasiowa, H. (1952) · Medical Entomology and Zoology · Cited by 4,307
(2004) · Choice Reviews Online · doi:10.5860/choice.41sup-0018 · Cited by 2,665
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
Gödel, K. (1931) · Monatshefte für Mathematik und Physik · doi:10.1007/bf01700692 · Cited by 2,395
Shoenfield, J. R. (1967) · Cited by 2,108
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
Gödel, K. (2006) · Monatshefte für Mathematik · doi:10.1007/s00605-006-0423-7 · Cited by 2,077
(1988) · Choice Reviews Online · doi:10.5860/choice.26-1932 · Cited by 1,777
An Unsolvable Problem of Elementary Number Theory
Church, A. (1936) · American Journal of Mathematics · doi:10.2307/2371045 · Cited by 1,763
Recursively Enumerable Sets and Degrees
Soare, R. I. (1987) · Perspectives in mathematical logic · doi:10.1007/978-3-662-02460-7 · Cited by 1,546
Self-citationMathematical Thought from Ancient to Modern Times
Kline, M. (1990) · doi:10.1093/oso/9780195061352.001.0001 · Cited by 1,171
Mathematical Thought from Ancient to Modern Times
Kline, M. (1990) · doi:10.1093/oso/9780195061376.001.0001 · Cited by 1,112
Computability and Unsolvability.
Elgot, C., & Davis, M. (1959) · Mathematical Tables and Other Aids to Computation · doi:10.2307/2002808 · Cited by 980
Webster's third new international dictionary of the English language, unabridged
GOVE, P. B. (1971) · Virtual Defense Library (Ministerio de Defensa) · Cited by 944
Recursively enumerable sets of positive integers and their decision problems
Post, E. L. (1944) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1944-08111-1 · Cited by 872
Formal Reductions of the General Combinatorial Decision Problem
Post, E. L. (1943) · American Journal of Mathematics · doi:10.2307/2371809 · Cited by 850
A note on the Entscheidungsproblem
Church, A. (1936) · Journal of Symbolic Logic · doi:10.2307/2269326 · Cited by 810
Hilbert, D. (1926) · Mathematische Annalen · doi:10.1007/bf01206605 · Cited by 776
On Notation for Ordinal Numbers
Kleene, S. C. (1938) · Journal of Symbolic Logic · doi:10.2307/2267778 · Cited by 758
From Frege to Gödel: a source book in mathematical logic, 1879-1931
van Heijenoort, J. (2021) · Cited by 733
On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction
Turing, A. M. (1938) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-43.6.544 · Cited by 600
Hilbert, D. (1922) · Vieweg+Teubner eBooks · doi:10.1007/978-3-663-15954-4 · Cited by 597
General recursive functions of natural numbers
Kleene, S. C. (1936) · Mathematische Annalen · doi:10.1007/bf01565439 · Cited by 593
Hodges, A. (1994) · Computerkultur · doi:10.1007/978-3-7091-9381-5 · Cited by 545
Systems of logic based on ordinals
(2001) · Mathematical Logic · doi:10.1016/b978-044450423-4/50007-3 · Cited by 543
Recursive Unsolvability of a problem of Thue
Post, E. L. (1947) · Journal of Symbolic Logic · doi:10.2307/2267170 · Cited by 534
Finite combinatory processes—formulation
Post, E. L. (1936) · Journal of Symbolic Logic · doi:10.2307/2269031 · Cited by 516
Systems of Logic Based on Ordinals†
Turing, A. M. (1939) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-45.1.161 · Cited by 504
Logic, Methodology and Philosophy of Science Proceedings of the 1960 International Congress
Nagel, E., Suppes, P., & Tarski, A. (1962) · Stanford University Press eBooks · Cited by 408
On undecidable propositions of formal mathematical systems
Gödel, K., Kleene, S. C., & Rosser, J. B. (1934) · Medical Entomology and Zoology · Cited by 391
The Universal Turing Machine A Half-Century Survey
(1995) · Computerkultur · doi:10.1007/978-3-7091-6597-3 · Cited by 373
Recursive predicates and quantifiers
Kleene, S. C. (1943) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1943-0007371-8 · Cited by 363
(1990) · Discrete Applied Mathematics · doi:10.1016/0166-218x(90)90034-a · Cited by 356
Computability: An Introduction to Recursive Function Theory
Cutland, N. J. (1980) · Medical Entomology and Zoology · Cited by 336
Church's Thesis and Principles for Mechanisms
(1980) · Studies in Logic and the Foundations of Mathematics · doi:10.1016/s0049-237x(08)71257-6 · Cited by 331
The Upper Semi-Lattice of Degrees of Recursive Unsolvability
Kleene, S. C., & Post, E. L. (1954) · Annals of Mathematics · doi:10.2307/1969708 · Cited by 269
λ-definability and recursiveness
Kleene, S. C. (1936) · Duke Mathematical Journal · doi:10.1215/s0012-7094-36-00227-2 · Cited by 267
Computability and λ-definability
Turing, A. M. (1937) · Journal of Symbolic Logic · doi:10.2307/2268280 · Cited by 262
The Oxford English Dictionary (Second Edition)
Swartz, J. J. (2013) · Per Linguam · doi:10.5785/5-1-452 · Cited by 228
Origins of Recursive Function Theory
Kleene, S. C. (1981) · IEEE Annals of the History of Computing · doi:10.1109/mahc.1981.10004 · Cited by 211
Computability: An introduction to recursive function theory
Cutland, N. (1980) · doi:10.1017/cbo9781139171496 · Cited by 206
Hierarchies of number-theoretic predicates
Kleene, S. C. (1955) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1955-09896-3 · Cited by 170
Mechanical Procedures and Mathematical Experience
Sieg, W. (1994) · doi:10.1093/oso/9780195079296.003.0005 · Cited by 129
The Confluence of Ideas in 1936
Gandy, R. O. (1990) · Oxford University Press eBooks · doi:10.1007/978-3-7091-6597-3_3 · Cited by 125
Why Gödel didn't have church's thesis
Davis, M. D. (1982) · Information and Control · doi:10.1016/s0019-9958(82)91226-8 · Cited by 124
Kleene, S. C., Barwise, J., Keisler, H. J., & Kunen, K. (1980) · Studies in logic and the foundations of mathematics · doi:10.1016/s0049-237x(08)x7060-0 · Cited by 119
Church, A. (1937) · Journal of Symbolic Logic · doi:10.1017/s002248120003958x · Cited by 115
Formal definitions in the theory of ordinal numbers
Church, A., & Kleene, S. C. (1937) · Fundamenta Mathematicae · doi:10.4064/fm-28-1-11-21 · Cited by 111
Copeland, J. (2017) · Oxford University Press eBooks · doi:10.1093/oso/9780198747826.003.0035 · Cited by 104
The Universal Turing Machine: A Half-Century Survey
(1990) · doi:10.1093/oso/9780198537748.001.0001 · Cited by 93
A. M. Turing's ACE report of 1946 and other papers
Carpenter, B. E., & Doran, R. W. (1986) · CERN Document Server (European Organization for Nuclear Research) · Cited by 89
The constructive second number class
Church, A. (1938) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1938-06720-1 · Cited by 83
The Word Problem in Semi-Groups With Cancellation
Turing, A. M. (1950) · Annals of Mathematics · doi:10.2307/1969481 · Cited by 78
The theory of recursive functions, approaching its centennial
Kleene, S. C. (1981) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-1981-14920-x · Cited by 61
Über den Zusammenhang der verschiedenen Begriffe der rekursiven Funktion
Péter, R. (1935) · Mathematische Annalen · doi:10.1007/bf01448046 · Cited by 46
Degrees of Unsolvability: Local and Global Theory
Lerman, M. (1983) · Project Euclid (Cornell University) · Cited by 41
Reflections on Church's thesis.
Kleene, S. C. (1987) · Notre Dame Journal of Formal Logic · doi:10.1305/ndjfl/1093637645 · Cited by 37
Turing-Machine Computable Functionals of Finite Types II†
Kleene, S. C. (1962) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s3-12.1.245 · Cited by 35
Mathematical Logic and the Origin of Modern Computers
Davis, M. D. (1995) · Computerkultur · doi:10.1007/978-3-7091-6597-3_5 · Cited by 33
Turing’s Analysis of Computability, and Major Applications of It
Kleene, S. C. (1995) · Computerkultur · doi:10.1007/978-3-7091-6597-3_2 · Cited by 31
Feferman, S. (1988) · Springer eBooks · Cited by 25
Computability theory, semantics and logic programming
Ringwood, G. A. (1988) · Science of Computer Programming · doi:10.1016/0167-6423(88)90069-x · Cited by 17
Mechanistic Theories in Cognitive Science: The Import of Turing’s Thesis
Tamburrini, G. (1997) · Springer eBooks · doi:10.1007/978-94-017-0487-8_13 · Cited by 11
The Mathematical Work of S.C.Kleene
Shoenfield, J. R. (1995) · Bulletin of Symbolic Logic · doi:10.2307/420945 · Cited by 11
Computability and Enumerability
Soare, R. I. (1997) · Springer eBooks · doi:10.1007/978-94-017-0487-8_12 · Cited by 6
Self-citation
Cited by
The Nature of Physical Computation
Shagrir, O. (2022) · doi:10.1093/oso/9780197552384.001.0001 · Cited by 70
Metadata
- Authors
- Soare, R. I.
- Venue
- Bulletin of Symbolic Logic
- Publisher
- Cambridge University Press (CUP)
- Published
- 1996-09
- Volume
- 2
- Issue
- 3
- Pages
- 284-321
- ISSN
- 1079-8986 (ISSN-L)
- 1943-5894
- OpenAlex
- W2132161762
- Cited by
- 268
- References
- 66
- FWCI
- 10.82
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.