Halting Problem

Origin. Turing (1936). The first proved-undecidable problem. Established by diagonalization, it grounds undecidability throughout logic and computer science.

Models. No algorithm decides, for an arbitrary program and input, whether the program halts. The halting set is semi-decidable but not decidable.

Formalism.

Halting sets: K = {e : φ_e(e)↓} (self-halting). K₀ = {⟨e, x⟩ : φ_e(x)↓} (general halting).

Diagonal argument: Suppose total h decides halting. Define d(e): if h(e, e) then diverge, else halt. Let d = φ_{e_d}. Ask whether d(e_d) halts. Halts iff it diverges — contradiction.

Semi-decidability: K is r.e.: run φ_e(e), accept if it halts. Not co-r.e.: non-halting is not confirmable.

Reduction principle: K ≤_m A ⟹ A undecidable. The standard route to new undecidability results.

Relativization: Halting relative to oracle A gives the jump A′. K ≡_T 0′.

Symbols.

Symbol	Unicode	Name	Meaning
↓	U+2193	Downwards arrow / Convergence	Computation halts
↑	U+2191	Upwards arrow / Divergence	Computation loops
⟨	U+27E8	Mathematical left angle bracket	Opens a coded pair
⟩	U+27E9	Mathematical right angle bracket	Closes a coded pair
′	U+2032	Prime / Turing jump	Halting relative to an oracle
⟹	U+27F9	Long double arrow / Implication	Consequence of a reduction
≡	U+2261	Equivalence	Turing equivalence, as in K ≡_T 0′
K	—	Halting set	Self-halting indices
K₀	—	General halting set	Halting on an arbitrary input
≤_m	—	Many-one reducibility	Reduction by a computable map on instances
φ_e	—	Index	e-th partial recursive function

Metatheory. Turing (1936) proved the unsolvability by diagonalization on the way to the Entscheidungsproblem; the name "halting problem" is Davis's, from 1958. K is Σ⁰₁-complete under many-one reduction — every r.e. set reduces to it — and Post (1944) showed K is creative, so by Myhill's theorem (1955) it is recursively isomorphic to every other creative set and is unique up to a computable permutation. Its complement is Π⁰₁-complete and not r.e., since a set and its complement both r.e. would make K recursive. Relativizing gives the jump: A′ is Σ⁰₁(A)-complete and A <_T A′ strictly, with K ≡_T ∅′. The undecidability transfers by reduction, and each transfer was a separate theorem: Post's correspondence problem (1946), the word problem for finitely presented groups (Novikov 1955, Boone 1957), the unconstrained domino problem (Berger 1966), and Hilbert's tenth problem via MRDP (Matiyasevich 1970). Radó's busy beaver function (1962) grows faster than every computable function precisely because computing it would decide halting for machines of a given size.

Applies to. Undecidability proofs. Limits of program analysis and verification. Foundations of computability. Complexity lower bounds by reduction.

Limitations. The theorem denies a single procedure uniform in the program; it does not say any particular instance is unknowable. For each fixed e the sentence "φ_e(e) halts" has a truth value and is very often provable, and the interesting failures are rarer than the statement suggests — though Yedidia and Aaronson (2016) did exhibit an explicit 7910-state machine that halts if and only if ZFC is inconsistent, so ZFC decides its behaviour only on pain of being inconsistent. Restricting the class restores decidability: halting is decidable for finite-state machines, for primitive recursive programs, and for any total-by-construction language, so the theorem raises no obstacle to languages designed to terminate. It forbids exactness, not usefulness, and leaves every sound incomplete static analysis intact. It supplies no resource information whatever, neither for the decidable fragments nor for the size of the numbers involved, which the busy beaver function shows to be non-computably large. And the diagonal argument produces one artificial instance: reaching a natural mathematical problem always required a further reduction, and those took decades.