Decidability & the Halting Problem
Some problems no computer can ever solve — not slowly, not with more RAM, ever. Here’s the proof, and why it matters.
Decidable vs Undecidable
A problem is decidable if some Turing machine always halts with the right yes/no answer. It’s undecidable if no machine can — not because we haven’t found the algorithm, but because a correct one provably cannot exist. This is a harder limit than “slow”: undecidable means impossible, on any hardware, with infinite time.
The Halting Problem
The famous undecidable problem: given a program P and input I, will P(I) halt or loop forever? No general algorithm can decide this for all P, I. Turing proved it in 1936 by contradiction:
# Suppose HALT(P, I) exists, returns true iff P(I) halts. def TROUBLE(P): if HALT(P, P): # does P halt when fed itself? while True: pass # ...then loop forever else: return # ...then halt # Now ask: does TROUBLE(TROUBLE) halt? # If it halts → HALT said it loops → contradiction # If it loops → HALT said it halts → contradiction
Either answer contradicts itself, so HALT cannot exist. The trick — feeding a program its own description — is diagonalization, the same technique Cantor used to prove some infinities are bigger than others.
Rice’s Theorem — It Gets Worse
Rice’s theorem generalizes the bad news: any non-trivial question about what a program computes (its behavior, not its text) is undecidable. “Does this program ever output 42?” “Does it compute a prime-checker?” “Is it equivalent to that other program?” All undecidable.
Where You Meet Undecidability in Practice
| Real question | Why it’s undecidable |
|---|---|
| Will this code ever terminate? | The halting problem itself |
| Is this code truly dead / unreachable? | Reduces to halting |
| Are these two functions equivalent? | Rice’s theorem |
| Does this program leak memory / this input? | Behavioral → Rice |
| Perfect antivirus (detect all malware)? | Behavioral → undecidable |
Engineers don’t give up — they approximate: bounded model checking, timeouts, conservative over-approximation, testing. The theory tells you when to stop looking for a perfect algorithm and reach for “good enough and sound”.
Interview Questions
Decidable vs undecidable vs recognizable?
Decidable: a TM always halts with the correct yes/no. Recognizable (semi-decidable): halts and says yes on yes-instances but may loop on no-instances. Undecidable: no TM decides it — impossible, not merely slow.
State and sketch the halting problem proof.
No algorithm decides whether an arbitrary program halts on an arbitrary input. Proof by contradiction: assume HALT exists, build TROUBLE(P) that loops iff HALT(P,P) says halt; asking whether TROUBLE(TROUBLE) halts contradicts either answer. Diagonalization.
What does Rice’s theorem say and why care?
Every non-trivial semantic property of a program’s behavior is undecidable. Practically: no tool can perfectly decide equivalence, termination, “ever outputs X”, or detect all malware — so real analyzers must be conservative approximations.
If halting is undecidable, how do linters/type checkers work?
They’re sound but incomplete approximations: they over-approximate the program’s behavior, reject some safe programs (false positives) to guarantee they never miss a real error class. They answer a decidable proxy, not the undecidable question.