TheoremProved

Undecidability of the halting problem

Statement

There is no algorithm that, given an arbitrary program (Turing machine) $P$ and input $x$ , always correctly decides in finite time whether $P$ halts when run on $x$ .

Why is it true?

Suppose such a halting-decider $H$ existed. Build a program $D$ that, on input a program $Q$ , runs $H$ to check whether $Q$ halts when run on itself, then does the opposite (loops forever if $Q$ halts, halts if $Q$ loops). Running $D$ on itself as input leads to a contradiction either way, so $H$ cannot exist.

Proof sketch

Diagonal argument: assume a decider $H(P,x)$ exists that outputs whether $P$ halts on $x$ ; define $D(P) =$ 'loop forever' if $H(P,P)$ says 'halts', else 'halt'; then ask whether $D(D)$ halts. If it halts, by definition $H(D,D)$ said 'loop forever', a contradiction; if it loops forever, $H(D,D)$ said 'halts', also a contradiction. So $H$ cannot exist.

Proved by

proved 1936Alan Turing

Topics that use this theorem

Recursive functions and Turing machines Gödel's incompleteness theorems

Related theorems

Gödel's first incompleteness theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Alan M. Turing (1936). On Computable Numbers, with an Application to the Entscheidungsproblem · DOI:10.1112/plms/s2-42.1.230
Michael Sipser (2012). Introduction to the Theory of Computation