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
K	—	Halting set	Self-halting indices
↓	U+2193	Halts	Computation converges
↑	U+2191	Diverges	Computation loops
≤_m	—	Many-one	Reduction

Metatheory. K is Σ⁰₁-complete: the hardest r.e. set. Its undecidability propagates by reduction to countless problems (tiling, word problems, Diophantine equations via MRDP, program verification). Rice's theorem generalizes it to all non-trivial semantic properties.

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

Limitations. Concerns worst-case general decision, not specific programs. Total-correctness heuristics succeed in practice on restricted classes. Says nothing about resources for the decidable part.