Technology
What is The halting problem?
The halting problem asks whether you can write one program that, for any program and input, always correctly says whether it will eventually stop or run forever. Alan Turing proved in 1936 that no such universal program can exist.
See it, don’t just read it.
Watch a 2-minute lesson with voice + animation that explains the halting problem.
Key things to understand
- 1It asks for a general way to predict if any program halts or loops forever.
- 2Turing proved it is impossible — no algorithm can decide it for every case.
- 3The proof uses a self-contradiction: a program that does the opposite of the prediction.
- 4It was among the first proofs that some problems are fundamentally unsolvable.
- 5It sets a hard limit on what automated software analysis can ever guarantee.
Frequently asked questions
- Why can't a program solve the halting problem?
- If one could, you could build a program that asks the solver about itself and then does the opposite — a contradiction, so no such solver exists.
- Does this mean some problems are unsolvable?
- Yes — the halting problem is the classic example of an 'undecidable' problem no computer can solve in every case.
- Why does the halting problem matter?
- It shows hard limits on automatic bug-checking: no tool can perfectly predict every program's behavior in advance.