The Halting Problem

Takeaway

There is no algorithm that decides for every program–input pair whether it halts; undecidability arises from self-reference and diagonalization.

The problem (before → after)

Before: Hope for a general “bug detector” that proves termination of any program.
After: A universal decider leads to a contradiction by constructing a program that halts iff it does not halt.

Mental model first

It’s like a librarian who promises to blacklist all books that mention themselves; you can always write a book that says, “This book is on the blacklist iff it is not on the blacklist,” breaking the promise.

Just-in-time concepts

Turing machines; encoding programs as data.
Diagonalization: Construct self-referential programs.
Reductions transfer undecidability.

First-pass solution

Assume HALT(P, x) decides halting. Define D(Q) = if HALT(Q, Q) then loop forever else halt. Apply D to itself to derive a contradiction.

Rice’s theorem generalizes undecidability to any nontrivial semantic property.
Practical termination: limited to specific languages or annotations.
Links to logic: Completeness limits mirror Gödel’s results.

Principles, not prescriptions

Some problems are provably beyond algorithmic reach; seek restricted domains.
Use reductions to map new problems to known undecidable ones.

Common pitfalls

Assuming undecidability means “hard in practice”; it’s a worst-case impossibility.
Confusing halting with runtime bounds.

Connections and contrasts

See also: [/blog/godels-incompleteness-theorems], [/blog/p-vs-np-problem], [/blog/rices-theorem-program-analysis].

Quick checks

Why self-application Q→(Q,Q)? — Enables diagonalization.
Does this kill static analysis? — No; it limits universality, not specialized analyses.
What does Rice’s theorem say? — Any nontrivial program property is undecidable.