The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
Computability: An introduction to recursive function theory
Abstract
What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). Dr Cutland begins with a mathematical characterisation of computable functions using a simple idealised computer (a register machine); after some comparison with other characterisations, he develops the mathematical theory, including a full discussion of non-computability and undecidability, and the theory of recursive and recursively enumerable sets. The later chapters provide an introduction to more advanced topics such as Gildel's incompleteness theorem, degrees of unsolvability, the Recursion theorems and the theory of complexity of computation. Computability is thus a branch of mathematics which is of relevance also to computer scientists and philosophers. Mathematics students with no prior knowledge of the subject and computer science students who wish to supplement their practical expertise with some theoretical background will find this book of use and interest.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Using Quine-like techniques, we construct an introspection program that simulates its own source code within an embedded virtual machine [22].”
From Self-Referential Introspection in Large Language Models: The Critical Threshold for Recursive Self-Improvement (2026) · cites this paper as [22]
Citations
Cites
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
Introduction to Metamathematics
Rasiowa, H. (1952) · Medical Entomology and Zoology · Cited by 4,307
Introduction to the Theory of Computation
Sipser, M. (1996) · ACM SIGACT News · doi:10.1145/230514.571645 · Cited by 2,784
Complexity of Computer Computations
(1972) · Springer eBooks · doi:10.1007/978-1-4684-2001-2 · Cited by 2,781
Computation: Finite and Infinite Machines.
Clarke, D. A., & Minsky, M. L. (1968) · The American Mathematical Monthly · doi:10.2307/2313471 · Cited by 2,583
Theory of Recursive Functions and Effective Computability
Cooper, D. C. (1969) · The Computer Journal · doi:10.1093/comjnl/12.1.28 · Cited by 2,539
A Decision Method for Elementary Algebra and Geometry
Tarski, A., & McKinsey, J. C. C. (1951) · University of California Press eBooks · doi:10.1525/9780520348097 · Cited by 1,206
The calculi of lambda-conversion
Rosser, B. (1941) · Medical Entomology and Zoology · Cited by 1,168
Handbook of Mathematical Logic
Beklemishev, L. D. (1977) · Cited by 1,036
Computability and Unsolvability.
Elgot, C., & Davis, M. (1959) · Mathematical Tables and Other Aids to Computation · doi:10.2307/2002808 · Cited by 980
Research works printed but not linked: 14
- Markov, 1954, The Theory of Algorithms, 42
- Bell, 1977, A Course in Mathematical Logic
- Péter, 1967, Recursive Functions
- Davis, 1965, The Undecidable
- Kleene, 1967, Mathematical Logic
- Brainerd, 1974, Theory of Computation
- Cobham, 1965, Proceedings of the 1964 International Congress for Logic, Methodology and Philosophy of Science, 24-30
- Van der Waerden, 1949, Modern Algebra, 1
- Gödel, 1931, Uber formal unentscheidbare Sätze der Principia Mathematica und verwandter System I, Monatschefte Math. Phys, 38, 173-98
- Church, 1936, Am. J Math, 58, 345-63
- Tarski, 1953, Undecidable Theories
- Cohn, 1977, Algebra,, 2
- Kleene, 1952, Introduction in Metamathematics
- Bird, 1976, Programs and Machines
Cited by
Cognitive Radio An Integrated Agent Architecture for Software Defined Radio
Mitola, J. (2000) · Cited by 3,470
Blackburn, P., Rijke, M. D., & Venema, Y. (2001) · Cambridge University Press eBooks · doi:10.1017/cbo9781107050884 · Cited by 1,689
Computability in Analysis and Physics
Pour-El, M. B., & Richards, J. I. (1989) · Perspectives in Mathematical Logic · doi:10.1007/978-3-662-21717-7 · Cited by 920
Software radio architecture: a mathematical perspective
Mitola, J. (1999) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.761033 · Cited by 372
Dosi, G., & Egidi, M. (1991) · Journal of Evolutionary Economics · doi:10.1007/bf01224917 · Cited by 342
Metadata
- Authors
- Cutland, N.
- Affiliations
- University of York (GB)
- Corresponding author
- Cutland, Nigel
- Venue
- Cambridge University Press eBooks
- Publisher
- Cambridge University Press
- Published
- 1980-06-19
- OpenAlex
- W4247585886
- Cited by
- 206
- References
- 34
- Citations by year
- 2026: 5 · 2025: 3 · 2024: 8 · 2023: 3 · 2022: 3 · 2021: 1 · 2020: 4 · 2019: 29 · 2018: 6 · 2017: 4 · 2016: 8 · 2015: 5 · 2014: 7 · 2013: 4 · 2012: 6
- FWCI
- 0.27
- Type
- book
- Language
- en
- Open access
- closed
- Locations
- Cambridge University Press eBooks (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Keywords
- computability theory, computability, recursive functions, register machines, undecidability, non-computability, computably enumerable sets, recursive sets, Gödel's incompleteness theorems, Turing degrees, recursion theorem
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Computability: An introduction to recursive function theory. https://app.cochat.ai/papers/10.1017/cbo9781139171496
- The paper
- Cutland, N. (1980). Computability: An introduction to recursive function theory. Cambridge University Press eBooks. https://doi.org/10.1017/cbo9781139171496
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.