Halting problem

The halting problem is the question Alan Turing proved unanswerable in 1936: given an arbitrary program and its input, does the program eventually halt, or run forever? Turing showed no general algorithm can decide this — not "we haven't found one yet," but a proof that none can exist.^[1]

The proof in one breath

Suppose a magic oracle halts(program, input) existed that always answered correctly. Build a program twist that asks the oracle about itself — and does the opposite: if the oracle says "twist halts," twist loops forever; if it says "twist loops," twist halts instantly. Now feed twist itself to the oracle. Whatever the oracle answers, twist makes it wrong — so the oracle cannot exist.^[2]

Why it matters

• Compilers can't perfectly detect infinite loops — they can only warn about patterns.
• Antivirus can't perfectly detect malicious programs — detection is bounded by decidability.
• Busy Beaver (Biggest numbers) is uncomputable precisely because solving it would solve halting.
• It defined the boundary of computation itself — the founding result of theoretical computer science, alongside Gödel's incompleteness theorems.

See also

• Biggest numbers
• Famous software bugs
• History of programming
• Alan Turing