The Halting Problem

We want a program H(P, x) that always halts and correctly answers "does P halt on x?". Note H is not allowed to simply run P — if P loops, so would H, and H must always return an answer.

The proof turns on one observation: a program is a finite string, so it can be passed to another program as data. That is not a trick — it is why compilers, interpreters and debuggers exist. In particular, H(P, P) is a perfectly sensible question.

1. 1Assume H exists.
2. 2Build D: given a program P, ask H whether P halts on P, then do the opposite — loop if H says halts, halt if H says loops.
3. 3D is clearly constructible: it is a call to H and an if-statement.
4. 4Now ask what D(D) does.
5. 5If H says D(D) halts, then D loops. H was wrong.
6. 6If H says D(D) loops, then D halts. H was wrong again.
7. 7There is no third case, so H cannot exist.

This does not say halting is hard to decide, or that we lack a clever enough algorithm. It says no algorithm exists, and no future machine changes that.

The halting language is still recognisable: simulate P on x, and if it halts you will eventually observe it. What is impossible is recognising the non-halting case — no amount of waiting distinguishes "has not halted yet" from "never will".

Halting is not a lone curiosity. Rice's theorem says every non-trivial property of what a program computes is undecidable — "does this throw?", "do these two functions agree?", "is this line ever reached?", "does this leak memory?".

That is why every real tool approximates. A type checker rejects programs that would in fact have run fine. A linter reports unreachable code conservatively. No compiler will tell you your loop terminates. These are not engineering failures to be fixed in the next release — they are this theorem, and the only question is which direction a tool chooses to be wrong in.

The standard way to prove some new problem undecidable is reduction: show that if you could solve it, you could solve halting. Since you cannot, you cannot solve the new one either.