The Halting Problem: A Task No Program Can Do
There is no program that can take any program and its input and always say correctly whether it will finish. The proof feeds the checker its own description, and the contradiction is where computability stops.
What a learner can do afterwards
- State the halting problem precisely, including what the checker is given
- Follow the self-reference step and say where the contradiction appears
- Tell an undecidable problem apart from one that is merely slow
1 · Read
An algorithm is a precise recipe: finite steps, clear instructions, and a guaranteed finish for every allowed input. The halting problem asks for a checker that receives any program plus its input and answers whether that program finishes. It must be right for every possible pair, with no exceptions.
Suppose the perfect checker existed. Build a trickster program that feeds its own description to the checker, then does the opposite of the verdict. Told it stops, the trickster loops forever. Told it loops, the trickster stops at once. The contradiction lands exactly at that self-asking step, so no verdict the checker gives can be right.
This strict standard is what lets the argument bite. A checker that works on most programs is not enough, because the proof builds its trap on the very case the checker claims to handle. One wrong answer breaks the guarantee, and the trickster finds it.
Keep undecidable apart from merely slow. A slow problem has a correct program that needs more time than the universe allows. An undecidable problem has no correct program at all, on any machine that will ever be built. When a task smells impossible, try the self-reference move before blaming your own skill.
No checker can call every halt, because the trickster always answers back wrong.
More to read
3.3 Formal Properties of Algorithms
An algorithm is a precise recipe: finite steps, clear instructions, and a guaranteed finish for every allowed input. Stating a problem precisely means naming exactly what the solver receives and what answer counts as correct. For the halting problem, the checker receives a program plus its input and must answer whether that program finishes.
This framing matters because vague claims hide the trap. A checker that works on most programs is not enough; it must be right for every possible program and input. Holding that strict standard is what lets the self reference argument bite.
3.6 Computer Science Theory
Theory asks what computers can do in principle, not just what runs fast today. Some problems are merely slow, needing more time than the universe allows, while others are undecidable: no program at all can solve them for every input. Telling those apart is one of the field's deepest skills.
The halting proof builds a trickster program that asks the supposed checker about itself, then does the opposite of the answer. If the checker says the trickster stops, it loops; if told it loops, it stops. The contradiction lands exactly at that self asking step, proving no perfect checker exists.
Theory of Computing: An Open Introduction
Theory of computing studies the outer limits of mechanical reasoning with simple models anyone can follow. It shows how to argue that a task is impossible, not just hard, by assuming a solver and deriving nonsense from it. The halting problem is the classic first example of this style.
Working through the proof trains a new reflex: when a task smells impossible, try the self reference move before blaming your own skill. Slow problems yield to faster machines or cleverer methods, but undecidable ones resist every machine that will ever be built. That boundary is permanent, and knowing it saves chasing ghosts.
Explore more
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
Optional connections
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.