Undecidability of the Halting Problem

The undecidability of the halting problem, proved by Turing in 1936, is one of the most fundamental results in mathematical logic and computer science. It establishes absolute limits on what can be computed.

Statement

Theorem5.1Undecidability of the Halting Problem

There is no Turing machine $H$ that, given an encoding $\langle M, w \rangle$ of a Turing machine $M$ and input $w$ , correctly decides whether $M$ halts on input $w$ . In other words, the set $\mathrm{HALT} = \{\langle M, w \rangle : M \text{ halts on } w\}$ is not decidable.

Proof

Suppose for contradiction that $H$ is a total Turing machine deciding HALT. Construct a new machine $D$ : on input $\langle M \rangle$ , $D$ runs $H(\langle M, \langle M \rangle \rangle)$ ; if $H$ accepts (meaning $M$ halts on $\langle M \rangle$ ), then $D$ loops forever; if $H$ rejects, then $D$ halts.

Now consider $D$ running on its own description $\langle D \rangle$ :

If $D$ halts on $\langle D \rangle$ , then $H(\langle D, \langle D \rangle \rangle)$ accepts, so $D$ loops. Contradiction.
If $D$ does not halt on $\langle D \rangle$ , then $H(\langle D, \langle D \rangle \rangle)$ rejects, so $D$ halts. Contradiction.

In either case we reach a contradiction, so $H$ cannot exist. $\square$

■

Consequences

ExampleSemantic Properties are Undecidable

The halting problem's undecidability immediately implies that many other questions about Turing machines are undecidable: "Does $M$ accept any input?", "Is the language of $M$ finite?", "Do $M_1$ and $M_2$ compute the same function?" All reduce from the halting problem.

RemarkComputational Universality

The proof exploits the ability of Turing machines to simulate other Turing machines (universality). This same self-referential structure appears in Gödel's incompleteness theorems. The connection is deep: undecidable problems correspond to independent statements in formal systems.