Computability Theory (Recursion Theory)

Origin. Gödel, Church, Turing, Kleene, Post (1930s). Formalize effective calculability. Several independently proposed models coincide. Foundation of the theory of the computable and the fourth branch of mathematical logic.

Models. Partial functions ℕ ⇀ ℕ. Computable = definable in some equivalent model (Turing machine, λ-calculus, μ-recursion). Church-Turing thesis identifies these with the intuitively effective. Study of what is computable, what is not, and computability relative to oracles.

Formalism.

Partial recursive functions: Initial: zero, successor, projections. Closure: composition, primitive recursion, minimization μ. Partial where μ may diverge.

Kleene normal form: Every partial recursive f: f(x) = U(μy. T(e, x, y)). T: primitive recursive Kleene predicate. U: result extractor.

Enumeration: φ_e: the e-th partial recursive function. Universal function: φ_univ(e, x) = φ_e(x). Effective listing of all programs.

s-m-n theorem: Primitive recursive s with φ_{s(e,x)}(y) = φ_e(x, y). Parameters can be fixed into indices.

Recursion (fixed-point) theorem: For total computable f, exists e with φ_e = φ_{f(e)}. Programs can refer to their own index.

Decidable vs semi-decidable: Recursive set: characteristic function computable. r.e. set: domain of a partial recursive function. A recursive iff A and complement both r.e.

Symbols.

Metatheory. Kleene's normal form theorem (1936) writes every partial computable function as U(μy T(e, x, y)) with T primitive recursive, so one unbounded search suffices; the same construction yields the enumeration theorem and a universal function. The s-m-n theorem makes parameter-fixing primitive recursive, and Kleene's second recursion theorem (1938) follows from it — for every total computable f some index e has φ_e = φ_{f(e)} — which is how a program obtains its own code. Post (1944) proved a set is recursive iff it and its complement are both r.e., and that K is Σ⁰₁-complete under many-one reduction; Rice (1953) extended undecidability to every non-trivial index set. Post's problem, whether an incomplete non-recursive c.e. degree exists, was settled independently by Muchnik (1956) and Friedberg (1957) by the finite-injury priority method, and Sacks (1964) proved the c.e. degrees dense. Matiyasevich (1970), completing work of Davis, Putnam and Robinson, proved the Diophantine sets are exactly the r.e. sets, so Hilbert's tenth problem is unsolvable.

Applies to. Foundations of computation. Proof theory. Definability. Undecidability results across mathematics. Theoretical computer science.

Limitations. The theory idealizes without bound — unlimited time and memory — so every decidable set counts as decidable at any cost, and Blum's speedup theorem shows the gap is worse than a missing dimension: there are computable functions for which no program is optimal, every program admitting one faster almost everywhere by any prescribed computable factor. The identification of the formal class with effective calculability is the Church–Turing thesis and is not a theorem. Priority constructions produce their sets by infinite approximation and describe membership only through the construction, so the standard existence results exhibit nothing. Most theorems are negative: Rice's theorem removes every non-trivial extensional property of programs from the decidable, so the subject rules out more than it supplies. And the structures it generates resist analysis — the first-order theory of the Turing degrees is recursively isomorphic to that of second-order arithmetic (Simpson 1977), and the theory of the c.e. degrees is undecidable (Harrington–Shelah 1982).

© 2026 Lingenic LLC