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.
2 · Watch
Take it off screen
Where it sits
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.