- Atlas
- Mathematics
- Recursion Theory
Recursion Theory
Recursion theory—also called computability theory—is the branch of mathematical logic that asks what it means for a procedure to be mechanical, and which problems such procedures can and cannot solve.
10 frameworks, from 1936 to today · Mathematical Logic · Mathematics
- Church–Turing thesis 1936-Present
- Undecidable problem 1936-Present
- Relative Computability and Degree Theory 1939-Present
- Arithmetical and Hyperarithmetical Hierarchies 1943-Present
- Computably Enumerable Sets and Reducibilities 1944-Present
- Computable Analysis and Computable Model Theory 1950-Present
- The Priority Method 1956-Present
- Higher Recursion Theory 1960-Present
- Algorithmic Randomness 1966-Present
- Reverse Mathematics 1970-Present
Overview
Recursion theory—also called computability theory—is the branch of mathematical logic that asks what it means for a procedure to be mechanical, and which problems such procedures can and cannot solve1. Its central objects are computable functions: functions from the natural numbers to the natural numbers that a finite, step-by-step rule could in principle evaluate without insight or luck12. The field grew from a foundational crisis—can all of mathematics be reduced to mechanical rules?—into a rich theory with its own hierarchies, a theory of relative computability of seemingly endless depth, and applications across mathematics and computer science. What is at stake is nothing less than the boundary between the decidable and the undecidable, and just how finely that boundary can be mapped.
The Entscheidungsproblem and the Race to Define "Computable," 1920s–1930s
David Hilbert's programme of the 1920s aimed to secure mathematics by formalizing it and showing, by finitary means, that the resulting system was consistent and complete3. A part of this programme was the Entscheidungsproblem—the decision problem—posed sharply by Hilbert and Wilhelm Ackermann in 1928: is there a mechanical procedure that, given any statement of first-order logic, decides whether it is valid45?
Before that could be answered, "mechanical procedure" had to be made mathematically precise. The 1930s produced several independent, and unexpectedly equivalent, formalizations4.
Kurt Gödel, in his 1931 incompleteness paper, defined the primitive recursive functions: those built from constants and the successor function by composition and recursion. These capture many arithmetical operations exactly, but Gödel, and later Jacques Herbrand and Gödel in private correspondence around 1934, pointed toward a broader notion involving unbounded searches. Stephen Kleene, working with Gödel's ideas, gave the generaeneral account in 1936: the recursive (later general recursive) functions are those definable by systems of equations allowing search, and Kleene showed the crucial equivalence with what Alonzo Church had defined independently.
Church's lambda calculus, developed in the early 1930s, was a formalism of function abstraction and application; a function of arithmetic is "lambda-definable" if it can be expressed in that calculus46. Meanwhile Alan Turing, in his 1936 paper "On Computable Numbers," introduced Turing machines—an idealized device with a tape of symbols and a finite set of rules, moving between a finite number of states47. Turing argued that a function is intuitively computable exactly when some Turing machine computes it, and he used the device to show the Entscheidungsproblem has no solution147. Church had reached the same negative conclusion earlier in 1936 via lambda definability; Emil Post, independently in the early 1920s, had sketched an equivalent analysis of symbol-manipulating processes, though his work was published only later.
The convergence of these radically different formalisms—Turing machines, lambda calculus, recursive functions—on the same class of functions led to what is now called the Church–Turing thesis: that these formalisms all capture precisely the intuitive notion of effective computability124. It is a thesis, not a theorem, because it equates a formal notion with an informal one; but the equivalence among the formalisms, established through results by Turing, Church, and Kleene in 1936, made the class look canonical. As a practical matter, it licensed recursion theorists to switch freely between machine-based, equation-based, and lambda-based definitions, choosing whichever made an argument clearest.
Undecidability: The Halting Problem and the First Great Negative Results
Turing's 1936 paper made precise the notion of a decision problem—a yes/no question about a class of inputs—and showed that some are undecidable: no Turing machine decides them. His central technique was the diagonal argument, adapted from Cantor and Gödel. Turing considered the set of machines that halt on a given input. A machine can be encoded as a number; so one can ask whether the machine with code e, run on input n, eventually halts. Turing showed that no single machine decides this question for all e and n—this is the halting problem, undecidable189. The proof proceeds by constructing, from any purported decider, a machine that defies it.
The same style of argument yields other landmark undecidability results. Church's theorem (1936) established the undecidability of first-order validity15. Kleene showed that the set of provable formulas of any consistent, sufficiently strong formal system is not decidable, sharpening Gödel's incompleteness theorems into a computability-theoretic form. This era also introduced computably enumerable (c.e., formerly "recursively enumerable") sets: those whose members can be listed by some machine110. A set is c.e. exactly when it is empty or the range of a computable function, and exactly when it is the domain of a partial computable function. Turing's and Post's formulations of the relationship between decidable, c.e., and co-c.e. sets became the organizing taxonomy of the next decades.
Post, in his 1944 paper "Recursively Enumerable Sets of Positive Integers and Their Decision Problems," posed a problem that would drive the field: are there c.e. sets of intermediate difficulty—neither decidable nor as hard as the halting problem? To pose the question precisely required a theory of relative difficulty.
Reducibilities and Degrees: Measuring the Unsolvable
The informal question "can problem A be solved by a machine that is given an oracle for problem B?" was made precise by Turing in 1939 through oracle machines: a Turing machine equipped with a black box that answers questions about a set B instantly111. A set A is Turing reducible to B (A ≤_T B) if a machine with oracle B decides A111. This relation generates Turing degrees: equivalence classes of sets under mutual reducibility, partially ordered by relative difficulty1. The degree of the halting problem, written 0′, is the jump of the computable sets—a canonical operation lifting a degree to the halting problem relative to it112.
Emil Post also introduced many-one reducibility (A ≤_m B if a computable function maps A into B), which is stricter than Turing reducibility and is central to the classification of c.e. sets113. The set of c.e. sets under many-one reducibility forms a structure whose exact shape became a major object of study. Post's 1944 paper conjectured that no c.e. set is strictly between the computable sets and the halting set in many-one degree—a conjecture that, fittingly, turned out to be false.
The 1950s brought the first deep structural results. Richard Friedberg (1957) and Albert Muchnik (1956), independently, solved Post's problem by constructing c.e. sets of incomparable Turing degree—incomparable meaning neither is reducible to the other—using the priority method. The priority method is an ingenious conflict-resolution technique: one builds a set by stages, with a list of requirements to satisfy; when two requirements conflict, the one with higher priority wins, variously114. It became the flagship technique of the field14. With it came the finite injury constructions, and later the infinite injury constructions needed for harder theorems.
The degree structure was then mapped in detail. C.E. degrees were shown to be dense (Sacks, 1964), to have infima (Lachlan and Yates, independently, mid-1960s), and to have unexpected rigidity and flexibility results. Later, in 1979, Leo Harrington and Saharon Shelah proved that there are first-order sentences true in the structure of degrees but not provable from certain natural axioms—an early result connecting recursion theory with set-theoretic independence. The jump operator and the Turing degree structure remain among the most studied algebraic objects in modern logic, with important theorems by Kirby, Slaman, and others in the 1980s–2000s, including the result (Slaman and Woodin) that the first-order theory of the degrees is not countably categorical in any strong sense and is highly complicated.
Hierarchies: Sorting the Computable and the Unsolvable
Parallel to degree theory, recursion theorists built hierarchies that stratify sets by the complexity of the definitions or processes generating them.
The arithmetical hierarchy classifies sets by how many unbounded quantifiers—alternating between "there exists" (existential) and "for all" (universal)—appear in a first-order definition over the natural numbers1516. The classes are Σ⁰₁ (c.e.), Π⁰₁ (co-c.e.), Σ⁰₂, Π⁰₂, and so on, with the halting problem at Σ⁰₁ and the jump iterates marching up the hierarchy. This was largely the work of Kleene, with foundational contributions in his 1943 and 1955 papers, and Mostowski and others filled in the picture.
The hyperarithmetic hierarchy extends this transfinite: it stratifies sets definable by iterating the jump through the computable ordinals (ordinals whose notation can be listed by a computable procedure). Kleene and Kreisel in the 1950s–60s developed this theory, which links recursion theory to descriptive set theory and to the study of definable real numbers. The c.e. sets are at the bottom, and on top sit sets definable by quantification over all arithmetical notions—or equivalently, by a single nonlinear quantifier.
Higher recursion theory extends computability beyond the natural numbers: to ordinals, to admissible sets, and to α-recursion (computability over an admissible set or ordinal α), developed by Gerald Sacks and others from the 1960s onward, with close ties to set theory (Kripke–Platek set theory). The key idea is preserving the closure properties that make ordinary recursion theory work—closure under primitive recursion and search—when the underlying domain is enlarged.
Post's own Turing degrees and the era's work on computably enumerable (c.e.) sets also produced the Turing jump hierarchy and the fine structure of c.e. degrees: the result by Sacks that c.e. degrees are dense, the existence of minimal pairs (Lachlan, 1966), and the non-existence of minimal c.e. degrees (proved by constructing c.e. sets of minimal c.e. degree—a landmark of the priority method). Each of these results required refining priority constructions—finite, infinite, and priority with injury—and their techniques spread to related fields.
Reverse Mathematics and the Modern Landscape
In the 1970s, Harvey Friedman initiated reverse mathematics, a programme asking: which set-existence axioms are needed to prove which classical theorems? The question is computability-theoretic in essence, because the strength of a theorem is gauged by what computable (or set-existence) principles it implies. Stephen Simpson's 1970s–80s work, culminating in the 1999 book Subsystems of Second-Order Arithmetic, systematized the field around a few benchmark systems—RCA₀, WKL₀, ACA₀, ATR₀, Π¹₁-CA₀—and showed that many theorems of analysis, algebra, and combinatorics fall into these classes. Reverse mathematics made precise the sense in which "the Bolzano–Weierstrass theorem is equivalent to weak König's lemma" and connected recursion theory to mainstream mathematics.
The same period saw algorithmic randomness emerge (from the work of Martin-Löf, 1966, and later Schnorr, Chaitin, and others), classifying sequences by the tests they fail; this connected computability to probability and information theory. Computable analysis and computable model theory grew as applied branches.
The field today is often called computability theory to signal its breadth beyond the classical recursion-theoretic core1. It descends directly from the 1930s work: Turing machines remain the default model for the Church–Turing thesis, and degree theory, hierarchy theory, and priority arguments remain the standard toolkit1. Open problems persist: the exact structure of the c.e. degrees (many questions about automorphisms of the degree structure, and the first-order theory of the degrees, remain open), the decidability of fragments of the theory of the degrees, and the precise relationship between degree-theoretic complexity and computational complexity in the resource-bounded setting. The Church–Turing thesis itself remains a thesis, its formalizations proven equivalent but its identification with intuitive computability fundamentally informal—a boundary the field has learned to live with, and to map from the inside.
References
- Computability theory (introduction, Turing computability, Introduction, Relative computability and the Turing degrees, Other reducibilities, The priority method, Name), Wikipedia
- Computable function, Wikipedia
- Hilbert's program, Wikipedia
- Church–Turing thesis (History, introduction), Wikipedia
- Entscheidungsproblem (introduction, History), Wikipedia
- Lambda calculus, Wikipedia
- Turing machine, Wikipedia
- Undecidable problem, Wikipedia
- Halting problem, Wikipedia
- Computably enumerable set, Wikipedia
- Turing reduction, Wikipedia
- Turing jump, Wikipedia
- Many-one reduction, Wikipedia
- Turing degree (Post's problem and the priority method), Wikipedia
- Arithmetical hierarchy, Wikipedia
- Post's theorem (Background), Wikipedia
The frameworks of Recursion Theory
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1936-Present
- 1936-Present
- 1939-Present
Relative Computability and Degree Theory
How hard is one problem relative to another?
- 1943-Present
Arithmetical and Hyperarithmetical Hierarchies
How do quantifiers stratify definable sets?
- 1944-Present
Computably Enumerable Sets and Reducibilities
What structure do listable sets have?
- 1950-Present
Computable Analysis and Computable Model Theory
Which mathematical objects are effectively computable?
- 1956-Present
- 1960-Present
Higher Recursion Theory
What is computability beyond the natural numbers?
- 1966-Present
- 1970-Present
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Undecidable problem grew out of Church–Turing thesis
Turing's 1936 analysis of computability via Turing machines was the direct vehicle for his proof that the halting problem and first-order validity are undecidable. The Church–Turing thesis supplied the canonical class of procedures against which undecidability is defined.
Carried by Alan Turing; On Computable Numbers (1936); Alonzo Church.
Relative Computability and Degree Theory grew out of Church–Turing thesis
Turing's 1939 oracle machines relativized the computable functions of the Church–Turing thesis to arbitrary sets, yielding Turing reducibility and degrees. Relative computability is the thesis's notion of effective procedure applied with an oracle.
Carried by Alan Turing; Systems of Logic Based on Ordinals (1939).
Computably Enumerable Sets and Reducibilities influenced by Undecidable problem
Post's 1944 paper on recursively enumerable sets and their decision problems built directly on the undecidability results, organizing c.e. sets by the difficulty of their decision problems. The taxonomy of decidable, c.e., and co-c.e. sets grew out of the halting-problem era.
Carried by Emil Post; Recursively Enumerable Sets of Positive Integers and Their Decision Problems (1944).
Computably Enumerable Sets and Reducibilities influenced by Relative Computability and Degree Theory
Post's many-one reducibility and his question about intermediate c.e. sets were posed in the framework of relative computability. The classification of c.e. sets by reducibility depends on the degree-theoretic notions Turing introduced in 1939.
Carried by Emil Post; Alan Turing.
The Priority Method influenced by Relative Computability and Degree Theory
The priority method was invented by Friedberg and Muchnik to solve Post's problem, constructing c.e. sets of incomparable Turing degree. It is a technique for building sets whose degrees satisfy requirements formulated in relative computability.
Carried by Richard Friedberg; Albert Muchnik.
Higher Recursion Theory grew out of Arithmetical and Hyperarithmetical Hierarchies
Higher recursion theory extends the arithmetical and hyperarithmetical hierarchies to admissible sets and higher-type objects, generalizing Kleene's quantifier classification. It grew directly out of the hyperarithmetical hierarchy as its set-theoretic and ordinal-theoretic generalization.
Carried by Stephen Kleene; Gerald Sacks.
The Priority Method influenced by Computably Enumerable Sets and Reducibilities
Post's problem, asking whether there are c.e. sets of intermediate many-one or Turing degree, was the direct target of the priority method. Friedberg and Muchnik's constructions answered it by building c.e. sets with prescribed degree properties.
Carried by Emil Post; Richard Friedberg; Albert Muchnik.
Computable Analysis and Computable Model Theory grew out of Church–Turing thesis
Computable analysis and computable model theory apply the Church–Turing thesis's class of computable functions to real numbers, continuous functions, and countable structures. They are the thesis's notion of effective procedure extended to analysis and model theory.
Carried by Alan Turing; Andrzej Grzegorczyk; Yiannis Moschovakis.
Arithmetical and Hyperarithmetical Hierarchies influenced by Undecidable problem
Kleene's arithmetical hierarchy was built to classify the sets definable by quantifier alternations, with the c.e. sets and halting problem as its first level. The undecidability results supplied the motivating examples at the bottom of the hierarchy.
Carried by Stephen Kleene; Recursive Predicates and Quantifiers (1943).
Reverse Mathematics influenced by Undecidable problem
Reverse mathematics measures the strength of theorems by the set-existence axioms needed to prove them, calibrated against computability-theoretic notions such as the halting problem and c.e. sets. Its base systems and first results were motivated by undecidability and effective mathematics.
Carried by Harvey Friedman; Stephen Simpson.
Higher Recursion Theory influenced by Relative Computability and Degree Theory
Higher recursion theory relativizes computability to higher types and admissible ordinals, using the degree-theoretic and oracle ideas of relative computability. The jump operator and reducibility notions were carried upward in this work.
Carried by Gerald Sacks; Stephen Kleene.
Reverse Mathematics influenced by Arithmetical and Hyperarithmetical Hierarchies
Reverse mathematics uses the arithmetical hierarchy and its proof-theoretic analogues to classify theorems by logical strength. The hierarchy of definable sets provided the model for the big-five subsystems of second-order arithmetic.
Carried by Harvey Friedman; Stephen Simpson.
Algorithmic Randomness influenced by Computably Enumerable Sets and Reducibilities
Algorithmic randomness was founded on the theory of c.e. sets and computable functions, using martingales and c.e. tests to define random sequences. The c.e. sets and their reducibilities supplied the basic computability-theoretic vocabulary for randomness notions.
Carried by Per Martin-Löf; Gregory Chaitin.
Beyond the field
Where Recursion Theory's ideas came from in other fields, and what they led to there: the strongest 12 of 40 links.
Church–Turing thesis influenced by General recursive function in Computability
Gödel's general recursive functions, developed from Herbrand's suggestions in 1934, supplied one of the formal explications that Church and Turing's thesis identified with effective calculability.
Carried by Kurt Gödel; Jacques Herbrand.
Church–Turing thesis influenced by Turing machine in Computability
Turing's 1936 machine analysis of computability provided the central formal notion that the Church–Turing thesis asserts to capture effective calculability.
Carried by Alan Turing; On Computable Numbers (1936).
Undecidable problem influenced by Turing machine in Computability
Turing's machine formalism was the vehicle for the first undecidability results, notably the halting problem and the Entscheidungsproblem, which define the framework.
Carried by Alan Turing; On Computable Numbers (1936).
Undecidable problem grew out of Turing machine in Computability
Turing's halting problem and his reduction of the Entscheidungsproblem to machine computation established the paradigm of undecidability proofs. Later undecidable problems are proved by reduction to his machine model.
Carried by Alan Turing.
Computably Enumerable Sets and Reducibilities influenced by Oracle Computability and Reducibility in Computability
Turing's oracle reducibility and Post's related reducibilities provided the reduction notions that organise the study of computably enumerable sets.
Carried by Alan Turing; Emil Post.
Computably Enumerable Sets and Reducibilities influenced Effective descriptive set theory in Descriptive Set Theory
The theory of computably enumerable sets and reducibilities supplied the basic notions (recursive, r.e., many-one and Turing reducibility) that effective descriptive set theory transferred from natural numbers to reals. Kleene's and Post's work on c.e. sets underlies the effective hierarchies.
Carried by Stephen Cole Kleene; Emil Post.
Church–Turing thesis influenced Oracle Computability and Reducibility in Computability
Oracle computability extends the Church–Turing thesis to relative computability, and the thesis's identification of effective with machine procedures is presupposed when relativising to an oracle. Turing's 1939 relativisation built on his 1936 analysis.
Carried by Alan Turing.
Church–Turing thesis influenced Turing degree in Computability
The Church-Turing thesis identifies the effectively computable functions with the Turing-computable ones, making Turing reducibility a canonical notion and the Turing degree a well-defined object. Degree theory rests on that identification.
Carried by Alonzo Church; Alan Turing.
Church–Turing thesis influenced Turing Test in Philosophy Of Artificial Intelligence
The recursion-theoretic formulation of the Church-Turing thesis gave the Turing test its background assumption that mechanical symbol processing is general. The test presumes a universal computing device.
Carried by Alan Turing; Alonzo Church.
Undecidable problem influenced Oracle Computability and Reducibility in Computability
Oracle computability and degree theory classify undecidable problems by relative difficulty, generalising the halting problem's unsolvability. Post's and Turing's work on degrees grew out of the study of undecidable problems.
Carried by Emil Post; Alan Turing.
Undecidable problem influenced Turing degree in Computability
The existence of undecidable problems, established by Turing and Church, motivated the comparison of sets by relative unsolvability, which yields Turing degrees. Post's and Kleene's degree work grew from questions about degrees of unsolvability.
Carried by Alan Turing; Emil Post.
Undecidable problem influenced by Church–Turing thesis in Computability
The Church–Turing thesis underwrites undecidability claims by identifying effective procedures with recursive or machine-computable ones, so that a negative result about machines yields unsolvability.
Carried by Alan Turing; Alonzo Church.

Recursion Theory is a planet in Nousfarer
Its city has a tower for each of these 10 frameworks. Land, walk in, and climb one concept at a time.
Land on Recursion TheoryRelated fields
Fields its ideas are linked to
- Computability 22 links
- Descriptive Set Theory 3 links
- Theory Of Computation 3 links
- Algorithms 2 links
- Mathematical Logic 2 links
- Logic 2 links
- Complexity Theory 2 links
- Randomized Algorithms 1 link
- Constructive Mathematics 1 link
- Philosophy Of Artificial Intelligence 1 link
- Automata 1 link
More in Mathematical Logic
- Constructive Mathematics
- Descriptive Set Theory
- Mathematical Logic
- Model Theory
- Proof Theory
- Set Theory
- Type Theory
See where Recursion Theory sits on the Map of Human Knowledge