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

still a working view ended · each leads to its entry below

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

  1. Computability theory (introduction, Turing computability, Introduction, Relative computability and the Turing degrees, Other reducibilities, The priority method, Name), Wikipedia
  2. Computable function, Wikipedia
  3. Hilbert's program, Wikipedia
  4. Church–Turing thesis (History, introduction), Wikipedia
  5. Entscheidungsproblem (introduction, History), Wikipedia
  6. Lambda calculus, Wikipedia
  7. Turing machine, Wikipedia
  8. Undecidable problem, Wikipedia
  9. Halting problem, Wikipedia
  10. Computably enumerable set, Wikipedia
  11. Turing reduction, Wikipedia
  12. Turing jump, Wikipedia
  13. Many-one reduction, Wikipedia
  14. Turing degree (Post's problem and the priority method), Wikipedia
  15. Arithmetical hierarchy, Wikipedia
  16. 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.

  1. 1936-Present

    Church–Turing thesis

    What exactly is a mechanical procedure?

    Fly to its tower in Nousfarer

  2. 1936-Present

    Undecidable problem

    Which problems can no machine decide?

    Fly to its tower in Nousfarer

  3. 1939-Present
  4. 1943-Present
  5. 1944-Present
  6. 1950-Present

    Computable Analysis and Computable Model Theory

    Which mathematical objects are effectively computable?

    Fly to its tower in Nousfarer

  7. 1956-Present

    The Priority Method

    How can conflicting requirements be met by stages?

    Fly to its tower in Nousfarer

  8. 1960-Present

    Higher Recursion Theory

    What is computability beyond the natural numbers?

    Fly to its tower in Nousfarer

  9. 1966-Present
  10. 1970-Present

    Reverse Mathematics

    Which axioms are needed to prove a theorem?

    Fly to its tower in Nousfarer

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.

Church–Turing thesisUndecidable problemRelative Computability and Degree The…Arithmetical and Hyperarithmetical Hi…Computably Enumerable Sets and Reduci…Computable Analysis and Computable Mo…The Priority MethodHigher Recursion TheoryAlgorithmic RandomnessReverse Mathematics

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.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Theory

Related fields

Fields its ideas are linked to

More in Mathematical Logic

See where Recursion Theory sits on the Map of Human Knowledge