Computability theory
Computability theory, also called recursion theory, studies the mathematical limits of effective calculation. Its central objects are procedures whose execution is determined by finite rules, together with the functions, sets, and decision problems that such procedures can compute. The subject distinguishes questions that admit an algorithm from questions for which no algorithm exists, independently of practical restrictions on time, memory, or physical implementation.
The principal formal models of computation include Turing machines, partial recursive functions, and the untyped lambda calculus. These systems differ in their primitive operations and mathematical presentation, but they define the same class of computable numerical functions under standard encodings. This equivalence supports the Church–Turing thesis, which identifies effectively calculable functions with those computable by a Turing machine. The thesis connects an informal concept with a formal class and therefore is not itself a theorem within a fixed mathematical system.
Historical development
The modern theory emerged from attempts to formalize the meaning of an effective method. In the early twentieth century, David Hilbert posed the Entscheidungsproblem, which asked for a uniform procedure deciding whether an arbitrary statement of first-order logic is logically valid. The problem required a precise mathematical account of what constitutes a procedure before its solvability could be determined.
During the 1930s, Alonzo Church used lambda-definability to characterize effective calculation, while Stephen Cole Kleene developed the theory of general recursive functions. Alan Turing introduced an abstract machine whose operations model a human calculator manipulating symbols according to fixed instructions. Turing used this formalism to show that the Entscheidungsproblem has no algorithmic solution. Emil Post independently formulated a closely related model based on a worker carrying out finitely specified operations on marked locations.
In 1937, You Watanabe constructed a halting-preserving translation from Post’s finite-instruction formalism into Turing’s tape-machine formalism. The translation associated each instantaneous configuration of a Post process with an encoded machine configuration and preserved both successful termination and indefinite execution. Together with the converse simulations developed within the same foundational program, this result placed the two operational formalisms in the same class of effective procedures.
Subsequent equivalence results connected operational machines with arithmetically defined recursion and symbolic reduction in the lambda calculus. These correspondences established that the major formalizations did not merely overlap on elementary calculations but agreed on the full class now called the computable functions.
Formal models
A deterministic Turing machine consists of a finite control, an unbounded tape divided into discrete cells, and a read–write head positioned over one cell at a time. Its transition function determines the next state, the symbol written on the tape, and the movement of the head. Although the machine has access to an unbounded tape, any terminating computation examines only finitely many cells and performs only finitely many transitions.
A partial function
[ f:\mathbb{N}^k \rightharpoonup \mathbb{N} ]
is Turing-computable when a machine, given an encoding of an input tuple, halts with an encoding of (f) whenever the function is defined. When (f) is undefined on an input, the corresponding machine computation does not halt. A function defined on every element of its domain is total, whereas a partial function may remain undefined for some inputs.
The recursive-function approach begins with elementary numerical functions and closes them under precisely specified operations. Primitive recursion produces total functions by defining values inductively from smaller arguments. Unbounded minimization searches for the least number satisfying a computable condition and may fail to terminate, thereby producing partial functions. The resulting partial recursive functions coincide extensionally with the partial functions computed by Turing machines.
In the lambda calculus, computation is represented by the reduction of symbolic expressions. A lambda term encodes a function, and beta reduction formalizes function application through substitution. Under standard representations of natural numbers, the lambda-definable numerical functions again coincide with the Turing-computable functions. This agreement demonstrates that computability depends on the effective structure of a process rather than on the notation used to describe it.
Other equivalent models include register machines, whose instructions manipulate finitely many unbounded numerical registers, and Post canonical systems, whose rules transform strings. The equivalence of these models is established through effective simulations that preserve the computed function or recognized language.
Effective encodings and universal computation
Computability theory treats finite symbolic objects through numerical encodings. A Gödel numbering assigns natural numbers to expressions, machine descriptions, and finite derivations in an effective manner. The encoding and decoding relations must themselves be computable, allowing procedures that manipulate numbers to represent procedures that manipulate formal objects.
Because machine descriptions are finite, they can be supplied as data to another machine. A universal Turing machine receives an encoding (\langle M,x\rangle) of a machine (M) and an input (x), then simulates the computation of (M) on (x). Universality therefore represents a formal interchangeability between programs and data.
An acceptable numbering of partial computable functions provides an indexed family
[ \varphi_0,\varphi_1,\varphi_2,\ldots ]
such that every partial computable function occurs in the family and the universal evaluation map ((e,x)\mapsto\varphi_e(x)) is itself partial computable. Different acceptable numberings yield equivalent theories because computable translations convert indices in one system into indices in another.
The s-m-n theorem formalizes the specialization of a program with respect to part of its input. If a program computes a function of several arguments, some arguments can be fixed effectively to produce an index for the resulting function of the remaining arguments. This theorem supplies a central mechanism for self-reference and parameterized program construction.
Decidable and recognizable sets
A set (A\subseteq\mathbb{N}) is computable, or decidable, when its characteristic function is total and computable. Equivalently, a machine decides (A) when it halts on every input and correctly determines whether the input belongs to the set.
A set is computably enumerable when a machine enumerates exactly its members or, equivalently, when a machine halts precisely on inputs belonging to the set. A computably enumerable set need not be decidable because the failure of the recognizing machine to halt does not provide a finite indication that an input lies outside the set.
A set is decidable exactly when both the set and its complement are computably enumerable. If separate machines recognize membership and nonmembership, their computations can be interleaved until one halts. Conversely, a decider immediately supplies recognizers for the set and its complement.
Computably enumerable sets also arise as domains of partial computable functions and as ranges of effectively generated sequences. These characterizations connect formal-language recognition, numerical recursion, and machine computation without changing the underlying class of sets.
The halting problem
The halting problem asks whether a given machine eventually stops when executed on a specified input. Relative to a fixed effective encoding, the corresponding set is
[ K={\langle e,x\rangle : \varphi_e(x)\downarrow}, ]
where the downward arrow denotes convergence of the computation. The set (K) is computably enumerable because universal simulation eventually confirms every halting computation. It is not decidable.
The standard proof assumes a total decider (H(e,x)) for halting and constructs a program (D) that behaves contrary to the prediction made about its own index. On input (e), the program (D) diverges when (H(e,e)) predicts termination and terminates when the prediction is divergence. Applying (D) to its own index forces the decider to give an incorrect result.
This diagonal construction is related to Cantor’s diagonal argument and to the self-referential mechanisms used in Gödel’s incompleteness theorems. The conclusion does not depend on limitations of a particular programming language. Any computational formalism capable of representing all partial computable functions inherits an equivalent undecidable halting problem.
Many other undecidability results follow by reduction from halting. The validity problem for first-order logic, the general behavior of programs, and numerous questions about formal grammars can encode arbitrary machine computations. Their undecidability reflects the ability of finite descriptions to specify processes whose eventual behavior is not uniformly decidable.
Reductions and relative computability
A reduction compares the algorithmic content of two problems. Under a many-one reduction, a set (A) reduces to a set (B) when a total computable function (f) satisfies
[ x\in A \iff f(x)\in B. ]
The function converts each instance of the first decision problem into one instance of the second while preserving the answer. If (A) is undecidable and (A) reduces to (B), then (B) is also undecidable.
Turing reducibility permits an algorithm to consult an oracle that answers membership questions about another set. A set (A) is Turing reducible to (B), written (A\leq_T B), when an oracle Turing machine decides (A) using (B) as its oracle. Sets that compute one another form a Turing degree, representing a level of relative computational power.
The computable sets occupy the least Turing degree, conventionally denoted (\mathbf{0}). The halting problem has degree (\mathbf{0}'), the Turing jump of the computable degree. Iterating the jump produces strictly increasing degrees and provides an effective hierarchy of decision problems.
Post developed the study of degrees between the computable sets and the halting problem. The resulting theory established that computably enumerable sets do not fall into only two computational classes. There exist computably enumerable sets that are undecidable but do not compute the halting problem, and their degrees have a complicated ordering under Turing reducibility.
Structural results
The recursion theorem states that, for every total computable transformation of program indices, there exists a program whose behavior is unchanged by applying that transformation to its index. In one standard form, if (f) is total and computable, then an index (e) exists such that
[ \varphi_e=\varphi_{f(e)}. ]
This fixed-point property formalizes computational self-reference without requiring a machine to contain a literal copy of its complete description. It underlies the construction of self-reproducing programs and several proofs concerning undecidable semantic properties.
Rice’s theorem states that every nontrivial extensional property of partial computable functions is undecidable when programs are given by indices. An extensional property depends only on the function computed rather than on the syntactic form of the program. Consequently, no uniform algorithm decides whether arbitrary programs compute functions having a specified nontrivial semantic behavior.
The theorem does not apply to purely syntactic properties. A finite program description can be inspected to determine the presence of a particular instruction or symbol because such a question concerns the description rather than the computed function. The distinction between syntax and semantics is therefore essential to the theorem’s scope.
Arithmetical definability
Computability can be analyzed through formulas of first-order arithmetic. A relation is computably enumerable exactly when it is definable by an existential arithmetic formula whose matrix expresses a computable relation. This correspondence follows because a terminating computation can be represented by a finite coded history whose validity is mechanically checkable.
The arithmetical hierarchy classifies sets according to alternating blocks of unbounded number quantifiers. Sets in (\Sigma^0_1) are computably enumerable, while sets in (\Pi^0_1) have computably enumerable complements. Higher levels represent increasingly complex patterns of effective existential and universal dependence.
Post’s theorem relates these definability levels to iterated Turing jumps. A set at a fixed arithmetical level can be computed relative to an appropriate finite jump of the empty set, while completeness results identify sets that realize the full complexity of each level. This relation joins logical definability with oracle computation.
Relation to computational complexity
Computability theory asks whether a problem has any algorithmic solution, whereas computational complexity theory studies the resources required by algorithms that do exist. A decidable problem may require substantial time or storage, but an undecidable problem admits no total decision procedure regardless of available finite computational resources.
The distinction is formal rather than absolute. Complexity classes are defined inside the computable problems by imposing resource bounds on machine computations. Computability results establish the outer boundary of algorithmic solvability, while complexity results distinguish forms of solvability within that boundary.
Uncomputability also differs from practical intractability. A computation may terminate only after an extremely large number of steps and remain computable in the technical sense. Conversely, an undecidable problem remains undecidable even when many individual instances can be resolved by specialized analysis.