AP® Computer Science Principles · Big Idea 3 · Topic 3.18
The Halting Problem
The halting problem shows there is no general algorithm that can look at any program and its input and correctly decide whether that program will eventually finish or run forever. This isn't a lack of cleverness — it's been proven impossible.
Suppose someone claims to have written a halt checker: a program H that takes any program P and input, and always correctly outputs 'halts' or 'loops forever.' The proof that this is impossible uses self reference. Build a new program called Weird that calls H on itself. If H says Weird halts, make Weird loop forever instead. If H says Weird loops forever, make Weird halt immediately. Now ask what H predicts when fed Weird as both the program and the input. Whatever H predicts, Weird does the opposite, so H is wrong. Since H was assumed to always be correct, this is a contradiction, which means no such H can exist.
The self reference is what makes this unbeatable. It isn't that H fails on some obscure edge case that a smarter design could patch. The trick builds a program specifically out of whatever H is, guaranteeing a contradiction no matter how H works internally. That's why the halting problem is called undecidable rather than just hard: no algorithm, however clever or however much time it's given, can solve it in general.
Real tools still watch for infinite loops, but they sidestep the impossible version of the question. A compiler might catch obvious cases, like a while loop whose condition never changes, or a debugger might just run code with a timeout and give up after a while, guessing 'probably stuck.' These are heuristics, not general solutions, and they can be wrong or simply refuse to answer. This connects the halting problem to the idea of problems that are solvable in principle but take unreasonable time: undecidable problems are a stronger kind of limit, where no algorithm exists at all, not just none that's fast.
Key terms
- Halting problem
- The question of whether a general algorithm can determine, for any program and input, if that program will eventually stop.
- Undecidable
- Describes a problem for which no algorithm exists that always gives a correct yes or no answer.
- Self reference
- Feeding a program itself as input, which is the trick used to build the contradiction in the halting proof.
- Heuristic
- A practical rule of thumb that often works but isn't guaranteed correct in every case.
Watch it explained
- How it worksWalk me through the contradiction that appears when a halt checker is fed itself.
- How it worksHow does self reference turn a perfectly plausible checking program into an impossibility?
- Going furtherWhat changes for real tools that try to detect infinite loops despite the halting problem?
- Common mistakeWhy doesn't the halting problem just mean nobody has been clever enough yet to write a working halt checker?
- Ties togetherHow does an undecidable problem differ from one that merely runs in unreasonable time?
Check yourself
End of topic.