Skip to content
Know.itKnow.it
Create an animated lesson
On request

This article is free to read. Creating a lesson uses your daily or stored credits; review the language and settings before starting.

What is the halting problem?

TechnologyLesson on requestFree to read

Quick answer

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. It asks for a general way to predict if any program halts or loops forever.

Key things to understand

  1. It asks for a general way to predict if any program halts or loops forever.
  2. Turing proved it is impossible — no algorithm can decide it for every case.
  3. The proof uses a self-contradiction: a program that does the opposite of the prediction.
  4. It was among the first proofs that some problems are fundamentally unsolvable.
  5. It sets a hard limit on what automated software analysis can ever guarantee.

People also ask

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.