Undecidability & the Halting Problem

the impossibility of a general halt checker

Here is the halting problem cashed out as practical advice for a programmer. There can be no tool that, given any program and input, always correctly reports whether the program will finish or hang. Not now, not with a faster computer, not ever — it is mathematically ruled out, not merely unbuilt. If someone claims to have written a perfect, universal infinite-loop detector that works on all code, they are mistaken, in the same way someone claiming a perpetual motion machine is mistaken.

This sounds discouraging, but the reality is more nuanced and more useful. The impossibility is only about a TOTAL and ALWAYS-CORRECT checker. In practice, useful approximate checkers exist and are everywhere: a tool may correctly prove termination for many programs, correctly prove non-termination for many others, and on the genuinely hard remainder give up honestly with 'I cannot tell'. This three-outcome design — yes, no, or don't-know — sidesteps the theorem, because the theorem only forbids a checker that must always commit to yes or no. Compilers, static analyzers, and termination provers do exactly this every day.

The deeper lesson is to budget your expectations correctly. You can verify termination for restricted languages (a language with only bounded loops always halts, trivially), for specific programs (with a hand proof or a ranking function), or with conservative tools that err on the safe side. What you cannot have is a single push-button oracle that settles termination for all conceivable code with no false answers and no abstentions. Knowing this saves you from chasing an impossible product and points you toward the achievable ones.

A real termination checker might report: 'while(i<n) i++; — proven to halt'; 'while(true){} — proven to loop'; 'collatz(n) — unknown'. The honest 'unknown' is what makes such tools possible despite the halting problem.

No total halt checker exists, but partial checkers that may answer 'don't know' are real and useful.

The theorem forbids a perfect always-deciding checker, not a helpful conservative one. Sound static analyzers thrive precisely by being allowed to answer 'maybe'.

Also called
no universal termination checkeryou cannot detect all infinite loops無通用停機檢查器無法偵測所有無窮迴圈