In 1928 the German David Hilbert set a challenge he called the Entscheidungsproblem, the “decision problem”: find a mechanical procedure that, given any mathematical statement written in the language of logic, would answer in finite time whether it is true or false. If it existed, mathematics would become an assembly line: just write down the question and turn the handle.

Hilbert believed the answer was yes. Eight years later, Turing and the American Alonzo Church showed, each by his own route, that it is no.

A simpler question

Turing did not attack Hilbert’s question head on. First he found a more modest question that no machine can answer. Today it is told like this:

Given a program and an input, will the program halt some day, or will it run forever?

Sometimes it is easy to know. A program that adds 1 to a number halts at once. A program that counts $1,2,3,\ldots$ with no way out never halts. But there are very short programs about which nobody knows the answer. This one, for example, tests the famous Goldbach conjecture, that every even number greater than 2 is the sum of two primes:

  1. Start with $n=4$.
  2. If $n$ is not the sum of two primes, halt.
  3. Otherwise, add 2 to $n$ and go back to step 2.

This program halts if and only if the conjecture is false. Knowing whether it halts means settling a problem open since 1742. A general method to decide whether programs halt would settle this one and many others at a stroke.

The proof

Suppose, for contradiction, that there is a machine $P$ that does the job. It receives the description of a program $M$ and an input $x$ and answers, always in finite time:

$$P(M,x)=\begin{cases}\text{“halts”}&\text{if }M\text{ halts on input }x,\\ \text{“does not halt”}&\text{if }M\text{ runs forever.}\end{cases}$$

With $P$ in hand, build a new machine, the contrarian $D$. It receives the description of a program $M$ and does the following:

  • it asks $P$ what $M$ does when it receives its own description as input;
  • if $P$ says “halts”, $D$ goes into an infinite loop;
  • if $P$ says “does not halt”, $D$ halts.

Now comes the fatal question: what does $D$ do when it receives its own description?

  • If $D(D)$ halts, then $P$ answered “does not halt” about $D(D)$, and $P$ was wrong.
  • If $D(D)$ does not halt, then $P$ answered “halts”, and $P$ was wrong again.

Either way, $P$ is wrong. So the machine $P$ does not exist. $\blacksquare$

The diagonal

This proof is a close relative of Cantor’s diagonal. Picture an infinite table in which row $i$ is the program $M_i$, column $j$ is the input “description of $M_j$” and each cell says whether the program halts. The machine $D$ looks only at the diagonal, the cells $(i,i)$, and does the opposite of each. That is why it cannot be any of the rows: it differs from row $i$ at least in cell $(i,i)$.

In the 1936 paper Turing did not use exactly the word “halt”: his question was whether a machine prints infinitely many digits or gets stuck halfway. The name “halting problem” came later, in the 1950s. The idea is the same. And from it Turing drew the answer to Hilbert: if there were a method to decide any logical statement, it would also decide the statement “the machine $M$ halts”, which is impossible.

Exercise: does this program halt?

Program: start with $n=7$. While $n\neq1$: if $n$ is even, $n\leftarrow n/2$; otherwise, $n\leftarrow3n+1$.

Follow it: $7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1$. It halts, after 16 steps. Nobody knows whether it halts for every starting $n$: this is the Collatz conjecture, open since 1937. Computers have checked it for enormous numbers, but checking cases is not proving.

Exercise: where does the proof use the machine P?

Explain why the proof does not say that “no program can be analysed”.

The proof only shows that there is no single method that is right for all programs. For many particular programs, deciding whether they halt is easy, and there are tools that do it every day. What does not exist is the universal machine $P$ that is never wrong and never fails to answer.

Sources: Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem” (1936) · Alonzo Church, “An unsolvable problem of elementary number theory”, American Journal of Mathematics (1936) · Martin Davis, The Universal Computer (2000).

All topics on Alan Turing · ← The Turing machine: calculating with pencil, tape and rules · Computable numbers: almost every number is impossible to calculate →

Image credits.