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.

Symbol	Unicode	Name	Meaning
φ_e	—	Index	e-th partial recursive function
⇀	U+21C0	Partial	Partial function
μ	U+03BC	Minimization	Least-witness operator
T	—	Kleene T	Computation predicate
↓ / ↑	—	Halts/diverges	Defined / undefined

Metatheory. Turing machines, λ-definability, general recursion, register machines all equivalent. Halting problem undecidable. Unsolvability stratified by Turing degrees and the arithmetical hierarchy. Robust under model variation.

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

Limitations. Idealized: unbounded time and memory. Church-Turing thesis not provable. Existence results often non-constructive. Says nothing about feasibility or complexity.