Skip to interview prep
Apexed

397. Why is the halting problem undecidable?

MediumComplexity classes

Technical
Show model answer

Suppose a program halts(P, x) always correctly answers whether program P halts on input x. Build a program D that, given P, runs halts(P, P) and then does the opposite: loop forever if the answer is 'halts', and halt otherwise. Now ask what D does on input D. If it halts, halts(D, D) said it halts, so D loops; if it loops, halts said it loops, so D halts. Both cases are contradictions, so no such halts can exist.

Undecidable is stronger than intractable: no algorithm at all decides the problem, regardless of time. Rice's theorem generalises this to every non-trivial property of a program's behaviour, which is why static analysers must accept false positives or false negatives. The halting problem is NP-hard but not in NP.

Why is the halting problem undecidable — Data structures & algorithms interview question — Apexed