The title of the 1936 paper does not talk about machines. It talks about numbers: “On computable numbers”. Turing defined them like this: a real number is computable when there is a machine that writes out, one after another, all of its digits, without ever getting any wrong.

Who is computable

Almost all the numbers that appear at school are computable.

  • Fractions: $\frac17=0.142857142857\ldots$ The machine does the long division and repeats the cycle forever.
  • Roots: $\sqrt2=1.41421356\ldots$ To find the next digit, the machine tests from 0 to 9 which is the largest that, when appended, still gives a number whose square does not exceed 2.
  • $\pi$ and $e$: there are series that approximate them as closely as we like, such as $e=1+\frac1{1!}+\frac1{2!}+\frac1{3!}+\cdots$, and with them a machine produces any digit, sooner or later.

It looks as if every “real” number is computable. And here comes the surprise: almost none is.

Machines can be counted

Every Turing machine is described by a finite table of rules. That table can be written as a text with a fixed alphabet and, therefore, as a single whole number, which Turing called a description number. Just replace each symbol by a digit.

So machines can be put in a list: the one with the smallest description number, the next one, and so on. Many numbers describe no machine at all, and many machines write no number at all, but that does not matter. What matters is that the computable numbers fit in a list $c_1,c_2,c_3,\ldots$ In technical language, they are countable.

The reals cannot be counted

In 1891 Georg Cantor showed that the real numbers do not fit in a list. The proof is the diagonal. Suppose a list of all the reals between 0 and 1:

$$\begin{aligned} r_1&=0.\underline{5}\,1\,3\,9\ldots\\ r_2&=0.2\,\underline{7}\,0\,4\ldots\\ r_3&=0.8\,8\,\underline{1}\,6\ldots\\ r_4&=0.3\,0\,2\,\underline{2}\ldots \end{aligned}$$

Build a number $d$ by changing the diagonal digit: where there is a 5, put 6; where there is any other digit, put 5. Here, $d=0.6555\ldots$ This $d$ differs from $r_1$ in the first place, from $r_2$ in the second, from $r_n$ in the $n$-th. It is not in the list. So no list contains all the reals.

Putting the two facts together: the computable numbers fit in a list, the reals do not. Reals are left outside every machine, and they are the vast majority. If you choose a real number at random, the probability that it is computable is zero.

Exercise: apply the diagonal

The list starts with $0.1234\ldots$, $0.5555\ldots$, $0.9090\ldots$, $0.3141\ldots$ Use the rule “5 becomes 6, everything else becomes 5” and write the first four digits of the diagonal number.

The diagonal is $1,5,9,1$. Changing them: $1\to5$, $5\to6$, $9\to5$, $1\to5$. The number is $0.5655\ldots$, which differs from each of the four in the diagonal place.

Exercise: 1/7 is computable

Describe in words the machine that writes out the digits of $\frac17$.

The machine keeps the remainder of the division, which can only be 1, 3, 2, 6, 4 or 5. At each step it multiplies the remainder by 10, writes the quotient by 7 and keeps the new remainder: $10=1\cdot7+3$, writes 1; $30=4\cdot7+2$, writes 4; $20=2\cdot7+6$, writes 2; and so on. As there are only six possible remainders, six states are enough, and the machine writes $142857$ forever.

Sources: Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem” (1936) · Georg Cantor, “Über eine elementare Frage der Mannigfaltigkeitslehre” (1891) · Charles Petzold, The Annotated Turing (2008).

All topics on Alan Turing · ← The halting problem: the question no machine can answer · The universal machine: the program is data too →

Image credits.