1.1 Early informal notions of algorithm
Long before the formalization of computability, mathematicians and philosophers grappled with the idea of an effective procedure. Ancient algorithms, such as Euclid’s algorithm for computing greatest common divisors (c. 300 BCE), embodied the notion of a step‑by‑step method guaranteed to yield a result. In the Middle Ages, Arabic mathematicians developed systematic methods for solving equations. The term “algorithm” itself derives from the name of the Persian mathematician al‑Khwarizmi (c. 780–850 CE). By the 19th century, mathematicians like Ada Lovelace and Charles Babbage envisioned mechanical computation, but a precise, universal concept of algorithm remained elusive.
1.2 Hilbert’s Entscheidungsproblem
In 1928, David Hilbert posed the *Entscheidungsproblem* (decision problem): is there an effective procedure that, given a logical statement expressed in a formal system, can determine whether it is universally valid (i.e., true in all interpretations)? This problem was part of Hilbert’s broader program to establish the consistency and completeness of mathematics through formal reasoning. Hilbert assumed that such a decision procedure existed, but the question was left open.
1.3 Gödel’s incompleteness theorems
In 1931, Kurt Gödel published his incompleteness theorems, which delivered a profound blow to Hilbert’s program. Gödel showed that any consistent formal system rich enough to express arithmetic contains true statements that cannot be proved within the system (first incompleteness), and that such a system cannot prove its own consistency (second incompleteness). While not directly about algorithms, these results hinted at inherent limitations of mechanical reasoning and inspired later work on undecidability.
1.4 Turing’s solution (1936)
Alan Turing, in his landmark 1936 paper “On Computable Numbers, with an Application to the *Entscheidungsproblem*,” provided a negative answer to Hilbert’s question. He introduced a formal model of computation—the Turing machine—and argued that any effectively calculable function could be computed by such a machine. Turing then proved that the halting problem (deciding whether a Turing machine will eventually halt on a given input) is undecidable, and from this he concluded that the *Entscheidungsproblem* is also undecidable. At nearly the same time, Alonzo Church independently reached the same conclusion using the lambda calculus, establishing the foundations of computability theory.
2.1 Formal models of computation
2.1.1 Turing machines
A Turing machine is an abstract device consisting of an infinite tape divided into cells, a read/write head, and a finite set of states. At each step, the machine reads the symbol in the current cell, transitions to a new state, writes a symbol, and moves the head left or right. Despite its simplicity, the Turing machine is capable of simulating any algorithm. The class of functions computable by a Turing machine is taken to be the class of effectively computable functions.
2.1.2 Partial recursive functions
The partial recursive functions are those that can be built from basic functions (zero, successor, projection) via composition, primitive recursion, and the unbounded minimization operator (μ‑recursion). A function is partial recursive if it can be defined using these operations, and it is total if it is defined for all inputs. This class coincides with the set of functions computable by Turing machines.
2.1.3 Lambda calculus
Alonzo Church’s lambda calculus is a notation for defining functions through variable binding and substitution. It uses a small set of rules (α‑conversion, β‑reduction) to compute results. The lambda calculus is equivalent in computational power to Turing machines: every lambda‑definable function is Turing‑computable and vice versa.
2.1.3.1 Church–Turing thesis
The Church–Turing thesis is the assertion that any function that is “effectively calculable” (in the informal sense) is computable by a Turing machine (or equivalently by the lambda calculus). It is not a rigorous theorem but a widely accepted working hypothesis that serves as the definition of computability. The thesis underpins all of computability theory.
2.2 Primitive recursive functions
Primitive recursive functions form a subclass of the total recursive functions. They are defined using only the operations of composition and primitive recursion (a restricted form of recursion where the recursion is over a single variable with a fixed depth). Examples include addition, multiplication, and factorial. Not all computable functions are primitive recursive—for instance, the Ackermann function grows faster than any primitive recursive function and is computable but not primitive recursive.
2.3 General recursive functions
General recursive functions extend primitive recursive functions by allowing the unbounded minimization operator (μ‑recursion). This operator searches for the smallest natural number satisfying a given condition; if no such number exists, the function is undefined for that input. The class of general recursive functions is exactly the class of partial recursive functions and is equivalent to Turing‑computable functions.
2.4 Characterizations of computability
Numerous models of computation have been shown to be equivalent in power: Turing machines, the lambda calculus, partial recursive functions, register machines, and many others. This convergence supports the Church–Turing thesis. Other formalisms, such as Markov algorithms and Post systems, also define the same class of computable functions. The standard characterization is that a function is computable if and only if it can be computed by a Turing machine.
3.1 Decidable problems
A decision problem (a set of yes‑or‑no questions) is decidable if there exists an algorithm that, for every instance, halts with the correct answer. Many natural problems are decidable, such as checking whether a given finite graph is bipartite, whether a propositional formula is satisfiable (using truth tables), or whether a given integer is prime. Decidable problems are those whose characteristic function is computable (a total recursive function).
3.2 Undecidable problems
An undecidable problem is one for which no algorithm can exist that always produces a correct answer. Since the 1930s, many important problems have been shown to be undecidable, often by reducing a known undecidable problem to them.
3.2.1 Halting problem
The halting problem asks: given the description of a Turing machine and its input, will the machine eventually halt? Turing proved in 1936 that no algorithm can solve this problem. The halting problem is the canonical undecidable problem.
3.2.1.1 Proof of undecidability via diagonalization
The proof uses a diagonal argument. Assume a halting decider \(H\) exists that, given a pair \((M, w)\), outputs “yes” if machine \(M\) halts on input \(w\) and “no” otherwise. Construct a new machine \(D\) that, on input \(M\), runs \(H(M, M)\) and then does the opposite: if \(H\) says “yes” (halts), \(D\) enters an infinite loop; if \(H\) says “no”, \(D\) halts. Now consider running \(D\) on its own description: \(D\) halts if and only if it does not halt—a contradiction. Hence no such \(H\) exists.
3.2.2 Rice’s theorem
Rice’s theorem states that any nontrivial property of the partial function computed by a Turing machine is undecidable. That is, if \(P\) is a set of partial recursive functions that is non‑empty and not equal to the whole set, then there is no algorithm that, given a Turing machine, decides whether its associated function belongs to \(P\). This shows that virtually all interesting semantic properties of programs are undecidable.
3.2.3 Post correspondence problem
The Post correspondence problem (PCP) asks whether, given a set of dominoes (pairs of strings), one can arrange them (with repetition allowed) so that the concatenated top string equals the concatenated bottom string. The problem was shown undecidable by Emil Post in 1946. PCP is often used to prove undecidability of other problems (e.g., in formal language theory) by reduction.
3.3 Recursively enumerable sets
A set \(A\) of natural numbers is recursively enumerable (r.e.) if there exists a Turing machine that enumerates its elements (i.e., that, running uninterrupted, outputs exactly the members of \(A\), possibly with repetitions). Equivalently, \(A\) is r.e. if it is the domain of some partial recursive function, or if it can be accepted by a Turing machine that halts on inputs in \(A\) and may run forever on inputs not in \(A\).
3.3.1 Properties of r.e. sets
The class of r.e. sets is closed under union, intersection, and the image under a partial recursive function. The complement of an r.e. set is r.e. if and only if the set is recursive (decidable). This yields the classic relationship: a set is recursive iff both it and its complement are r.e. Many natural problems, including the halting set (pairs \((M,w)\) where \(M\) halts on \(w\)), are r.e. but not recursive.
3.3.2 Creative and productive sets
A creative set is an r.e. set whose complement is productive. A set \(P\) is productive if there exists a partial recursive function \(f\) that, given any r.e. subset \(W\) contained in the complement of \(P\), produces an element in the complement of \(P\) that is not in \(W\). Creative sets are “universal” in the sense that every r.e. set can be many‑one reduced to the halting set. The halting set itself is creative. These concepts are central to the study of complete sets and effective inseparability.
4.1 Turing reducibility
Turing reducibility formalizes the idea of one problem being solvable given an oracle for another problem. A set \(A\) is Turing‑reducible to \(B\) (written \(A \leq_T B\)) if there is an oracle Turing machine that, when given the characteristic function of \(B\) as an oracle, can compute the characteristic function of \(A\). This concept, introduced by Turing in 1939, allows one to compare the relative difficulty of undecidable problems.
4.1.1 Definition and oracle machines
An oracle Turing machine is a Turing machine augmented with an extra “oracle” tape that can ask membership queries about an arbitrary set \(B\). When the machine enters a special query state, it receives a yes/no answer indicating whether a given number is in \(B\). The machine then continues normally. If the machine halts on every input and always gives the correct answer for \(A\) when using oracle \(B\), then \(A\) is Turing‑reducible to \(B\).
4.2 Turing degrees
A Turing degree (or degree of unsolvability) is an equivalence class of sets under mutual Turing reducibility: two sets have the same degree if each is reducible to the other. The degree of recursive (decidable) sets is called \(0\). Degrees above \(0\) correspond to problems that are effectively unsolvable but of varying “difficulty”.
4.2.1 Structure of the Turing degrees
The set of all Turing degrees forms a partial order under \(\leq_T\). The structure is a distributive lattice with a least element \(0\). It has many interesting properties: it is dense (between any two degrees there is another), it has uncountably many elements, and it is not a total order (incomparable degrees exist). The degrees are also closed under the jump operator.
4.2.2 Jump operator
The jump of a set \(A\), denoted \(A'\), is the set of indices of oracle Turing machines that halt when given the oracle \(A\) (i.e., the halting problem relativized to \(A\)). The jump operator maps degree \(\mathbf{a}\) to a strictly larger degree \(\mathbf{a}'\). Iterating the jump yields a strictly increasing sequence: \(0 < 0' < 0'' < \cdots\). The jump operator is a key tool for analyzing the complexity of problems.
4.2.3 Minimal degrees
A minimal degree is a nonzero Turing degree such that no nonzero degree is Turing‑reducible to it. The existence of minimal degrees was proved by Spector in 1956. Minimal degrees are “very small” among the nonrecursive degrees, and their existence shows that the structure of degrees is complex and nontrivial.
4.3 Many-one and other reducibilities
While Turing reducibility is the most general, other more restrictive reducibilities are also studied.
4.3.1 Many-one degrees
A set \(A\) is many‑one reducible to \(B\) (written \(A \leq_m B\)) if there exists a total computable function \(f\) such that \(x \in A \iff f(x) \in B\). Many‑one reducibility is stronger than Turing reducibility: if \(A \leq_m B\) then \(A \leq_T B\), but the converse may fail. Many‑one degrees are equivalence classes under mutual many‑one reducibility. They are used, for example, to classify the complete sets for the arithmetical hierarchy.
4.3.2 Truth-table degrees
Truth‑table reducibility refines many‑one reducibility by allowing the reduction procedure to ask a bounded number of oracle queries, with the result determined by a truth table. A set \(A\) is truth‑table reducible to \(B\) if there is a computable function that, given an input \(x\), produces a truth table and a list of candidate queries to \(B\), such that \(x \in A\) iff the truth table evaluates to “true” when the answers to the queries are supplied. Truth‑table degrees provide a finer classification than many‑one degrees but are less general than Turing degrees.
5.1 Abstract computability
5.1.1 Generalized recursion theory
Generalized recursion theory extends the concepts of computability to arbitrary structures beyond the natural numbers. It studies the notion of “computable” on sets with additional structure, using ideas like the “computable” subsets of an arbitrary first‑order structure. This area connects recursion theory to model theory and set theory.
5.1.2 E-recursion and α-recursion theory
E‑recursion (set recursion) and α‑recursion theory investigate computability on the transfinite ordinals and on admissible sets. In α‑recursion theory, one replaces the natural numbers with a fixed admissible ordinal α and defines α‑recursive functions analogously. These theories extend the methods of classical recursion theory to higher recursion and reveal the structure of definability in set theory.
5.2 Computability on the reals
5.2.1 Computable real numbers
A real number \(x\) is computable if there is a Turing machine that, given a rational error bound \(\epsilon > 0\), outputs a rational approximation within \(\epsilon\) of \(x\). All familiar constants (e.g., \(\pi\), \(e\), \(\sqrt{2}\)) are computable. However, the set of computable reals is countable, and most reals are not computable. Computable reals form a real closed field.
5.2.2 Computable analysis
Computable analysis studies functions on the reals that can be approximated algorithmically. A function \(f: \mathbb{R} \to \mathbb{R}\) is computable if there is an oracle Turing machine that, given a rational approximation for an input real, produces a rational approximation for the output real. Many standard functions (addition, multiplication, sine) are computable in this sense, but discontinuous functions generally are not.
5.2.2.1 Real computation and the BSS model
The Blum–Shub–Smale (BSS) model of computation treats real numbers as atomic objects and allows exact arithmetic operations and comparison. In this model, one can define computability over the reals directly, and many results from classical recursion theory (e.g., undecidability of the halting problem) have analogs. However, the BSS model is non‑effective in the classical sense because it assumes infinite precision.
6.1 Arithmetical hierarchy
6.1.1 Classification of formulas
The arithmetical hierarchy classifies first‑order formulas of Peano arithmetic by the number and alternation of unbounded quantifiers. A formula is \(\Sigma^0_n\) if it begins with a block of \(n\) alternating quantifiers starting with an existential, and is \(\Pi^0_n\) if it starts with a universal. The hierarchy stratifies the definable sets of natural numbers: a set is \(\Sigma^0_1\) if it is definable by an existential formula (i.e., it is r.e.), and it is \(\Delta^0_1\) if it is both \(\Sigma^0_1\) and \(\Pi^0_1\) (i.e., decidable).
6.1.2 Post’s theorem
Post’s theorem (1948) connects the arithmetical hierarchy with Turing degrees. It states that a set is \(\Sigma^0_{n+1}\) if and only if it is recursively enumerable relative to the \(n\)‑th jump of the empty set (i.e., \(∅^{(n)}\)). Moreover, the jump operator corresponds exactly to moving up one level in the hierarchy. This theorem provides a recursion‑theoretic characterization of the arithmetical definability.
6.2 Computable model theory
Computable model theory studies the content and complexity of model‑theoretic constructions from the perspective of computability. It asks, for a given mathematical structure, whether its isomorphism type contains a computable copy, or whether certain model‑theoretic properties (e.g., completeness, categoricity) can be effectively recognized. Classic results include the existence of computable but not decidable theories and the fact that every countable Boolean algebra has a computable presentation.
6.3 Relation to computational complexity theory
6.3.1 Polynomial-time computability vs. decidability
While classical recursion theory asks whether a problem is solvable at all (decidable), computational complexity theory asks how efficiently it can be solved (e.g., in polynomial time). Decidable problems may be intractable (e.g., exponential‑time); undecidable problems are clearly intractable. Recursion theory provides the intellectual foundation for distinguishing computable from non‑computable problems, while complexity theory further refines the classification of the computable ones.
6.3.2 Complexity classes and recursion theory
Recursion‑theoretic concepts, such as reducibility and completeness, have natural analogs in complexity theory (e.g., polynomial‑time reducibility and NP‑completeness). The arithmetical hierarchy also inspires the polynomial hierarchy. Moreover, the concept of oracle machines from recursion theory is directly used to define relativized complexity classes (e.g., \(P^{NP}\)) and to explore separations between complexity classes. Recursion theory also contributes to the study of resource‑bounded measure and genericity.
7.1 Computability in theoretical computer science
Computability theory underpins many areas of computer science. It provides the formal basis for the analysis of algorithms, the limits of automatic programming, and the theory of parsing and formal languages (the Chomsky hierarchy relates grammars to Turing machines). It is also essential in the study of verification, where undecidability results imply that full automation of correctness proofs for arbitrary programs is impossible.
7.2 Recursive functions in programming languages
Recursive function definitions are a fundamental construct in nearly all programming languages. The concept of recursion as captured by partial recursive functions is directly reflected in language features like recursion, anonymous functions (lambda abstraction), and fixed‑point combinators. Many languages implement recursion via stack‑based mechanisms, and the theoretical limitations (e.g., stack overflow) relate to the distinction between total and partial recursion.
7.3 Limitations of automated theorem proving
Gödel’s incompleteness theorems and undecidability results directly limit the scope of fully automated theorem proving. No algorithm can decide the truth of all statements of arithmetic, and no complete and consistent axiom system for arithmetic can exist. In practice, automated theorem provers must work with incomplete methods, heuristics, or human‑assisted interactive proofs. The halting problem also implies that it is impossible to detect all infinite loops in programs automatically.
7.4 Open problems and contemporary directions
Several open problems remain in recursion theory. For example, the question of whether minimal Turing degrees exist above every degree is settled, but many structural conjectures about the degrees are still open (e.g., the bi‑interpretability of the partial order of degrees with true arithmetic is known, but fine details remain). Higher‑order computability, the study of the effective content of descriptive set theory, and the relationships with randomness (algorithmic information theory) are active areas. The influence of recursion theory also extends to new domains such as quantum computability and biological computation.