How Did Turing Prove the Halting Problem Is Undecidable?

Alan Turing proved in 1936 that no general algorithm can determine whether an arbitrary computer program will eventually stop or run forever. He reached this conclusion by combining a proof by contradiction with a diagonalization argument inspired by Georg Cantor. By assuming that a universal halting decider could exist, Turing constructed a paradoxical program that forces the decider to contradict itself.

What Is the Halting Problem?

In classical computing, a program can be modeled as a Turing machine \(M\) that takes an input string \(w\). When \(M\) runs on \(w\), one of two outcomes occurs:

  1. The machine halts after a finite number of steps and produces an output.
  2. The machine runs forever in an infinite loop.

The Halting Problem asks whether there exists a single, general algorithm—a Turing machine \(H\)—that can take any pair \(\langle M, w \rangle\) and reliably output:

\[H(\langle M, w \rangle) = \begin{cases} \text{accept} & \text{if } M \text{ halts on } w \\ \text{reject} & \text{if } M \text{ loops forever on } w \end{cases}\]

Crucially, \(H\) itself must always halt on every possible input \(\langle M, w \rangle\).

The Assumption for Contradiction

To prove that no such machine \(H\) can exist, Turing began by assuming the opposite: suppose \(H\) does exist. Because any Turing machine can be encoded as a finite string of symbols (its description \(\langle M \rangle\)), a machine can take its own description as input.

Using \(H\) as a subroutine, we can construct a new Turing machine \(D\) (for "diagonal") that takes a single machine description \(\langle M \rangle\) as input and behaves as follows:

  1. Run \(H\) on \(\langle M, \langle M \rangle \rangle\) to ask whether \(M\) halts when given its own description as input.
  2. If \(H\) outputs accept (meaning \(M\) halts on \(\langle M \rangle\)), then \(D\) deliberately enters an infinite loop.
  3. If \(H\) outputs reject (meaning \(M\) loops forever on \(\langle M \rangle\)), then \(D\) immediately halts.

In other words, \(D\) does the exact opposite of whatever \(H\) predicts \(M\) will do when fed its own code.

The Diagonalization Step

Now consider what happens when we run \(D\) on its own description, \(\langle D \rangle\). Because \(D\) is a valid Turing machine, \(\langle D \rangle\) is a valid input. Evaluating \(D(\langle D \rangle)\) leads to an inescapable contradiction:

  • Case 1: Suppose \(D\) halts on \(\langle D \rangle\). Then \(H(\langle D, \langle D \rangle \rangle)\) must output accept. By the definition of \(D\), however, when \(H\) outputs accept, \(D\) enters an infinite loop. So \(D\) does not halt on \(\langle D \rangle\).
  • Case 2: Suppose \(D\) loops forever on \(\langle D \rangle\). Then \(H(\langle D, \langle D \rangle \rangle)\) must output reject. By the definition of \(D\), when \(H\) outputs reject, \(D\) halts. So \(D\) halts on \(\langle D \rangle\).

In both cases, \(D(\langle D \rangle)\) halts if and only if it does not halt.

Why This Is Called Diagonalization

Turing's construction mirrors Georg Cantor's diagonal argument for the uncountability of the real numbers. Imagine an infinite table where the rows represent all possible Turing machines \(M_1, M_2, M_3, \dots\) and the columns represent their encodings \(\langle M_1 \rangle, \langle M_2 \rangle, \langle M_3 \rangle, \dots\). Each cell \((i, j)\) records whether machine \(M_i\) halts on input \(\langle M_j \rangle\).

The machine \(D\) looks at the main diagonal of this table—the cells \((i, i)\) where each machine is tested on its own encoding—and flips every entry. If \(M_i\) halts on \(\langle M_i \rangle\), \(D\) loops; if \(M_i\) loops on \(\langle M_i \rangle\), \(D\) halts. Because \(D\) differs from every machine \(M_i\) on at least the diagonal entry \(\langle M_i \rangle\), \(D\) cannot appear anywhere in the list of all Turing machines—contradicting the assumption that \(H\) exists to build it.

Conclusion

Since the existence of \(D\) follows directly from the existence of \(H\), and \(D\) produces a logical contradiction, the original assumption must be false. Therefore, no Turing machine \(H\) can exist, and the Halting Problem is undecidable in classical computing.