The Paper Tape and the Uncomputable Number

How a Mechanical Clerk Destroyed David Hilbert's Dream of Complete Decidability

Proving that a mechanical procedure exists to solve a mathematical problem is straightforward. One simply writes down the algorithm and demonstrates that it halts with the right answer. Proving that no mechanical procedure can ever exist to solve a problem is vastly harder. Before 1936, mathematics possessed no rigorous definition of what a mechanical procedure or calculation actually was. To prove that David Hilbert's Entscheidungsproblem was unsolvable, Alan Turing first had to translate the intuitive notion of a human clerk following rules into an exact mathematical object.

Lying in the grass at Grantchester meadows outside Cambridge in the summer of 1935, Turing stripped human calculation of every inessential feature. A human clerk computing a number at a desk uses two-dimensional sheets of squared paper. The clerk looks at a few digits at a time, keeps a mental note of what step to perform next, and writes down new digits. Turing realized that two dimensions of paper are unnecessary. A single one-dimensional strip of paper tape divided into discrete squares can store any arrangement of symbols.

In his 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem, published in the Proceedings of the London Mathematical Society, Turing defined his $a$-machine, now called a Turing machine. The device consists of an unbounded paper tape divided into squares, a scanning head that reads and writes one square at a time, a finite alphabet of tape symbols, and a finite set of internal states $q_1, q_2, \dots, q_k$. At each discrete clock step, the pair $(q_i, S_j)$ of current state and scanned symbol fixes the machine's next action. The head writes a specified symbol on the current square, shifts one square left ($L$) or right ($R$), and enters state $q_m$.

Turing defined a real number as computable if its infinite binary expansion of 0s and 1s can be printed square by square by a machine with a finite state table. Because every state transition rule is just a short string of letters and semicolons, Turing replaced each state, symbol, and direction with one of seven digits (1 through 7). Every possible Turing machine $M$ then collapses into a single finite integer called its description number $D(M)$.

That integer encoding yielded two consequences that transformed science. First, because the rules of any machine $M$ can be written as a number $D(M)$ on a paper tape, engineers do not need to build separate physical machines for multiplication, differential equations, and chess. Turing wrote out the explicit state table for a single Universal Turing Machine $U$. Given a tape containing the description number $D(M)$ of any target machine $M$, the universal machine $U$ reads the encoded instructions and simulates $M$ step by step.

Second, Turing turned Georg Cantor's 1891 diagonal argument against the list of description numbers. Since every description number $D(M)$ is an integer, the set of all possible Turing machines is countable. Suppose a decision machine $H$ existed that could inspect any integer $n$ and decide in finite steps whether $n$ describes a circle-free machine that prints an infinite sequence of binary digits $\phi_n(1), \phi_n(2), \dots$ without stalling. One could then program a master machine $B$ to test $n = 1, 2, 3, \dots$ in order. At each step $n$, machine $B$ simulates the $n$-th circle-free machine using $U$ until it computes its $n$-th digit $\phi_n(n)$, and then prints the inverted digit $1 - \phi_n(n)$.

Because machine $B$ follows a finite mechanical rule, $B$ must possess its own description number $K$ in the list. What happens when $B$ reaches step $K$ and attempts to compute the $K$-th digit of its own output? To compute $\phi_K(K)$, the decision sub-machine $H$ must first finish deciding whether $K$ itself is circle-free, triggering an infinite self-referential regress. Therefore, no mechanical procedure can decide whether an arbitrary machine ever halts or prints a given symbol 0. Translating the tape transitions of any machine $M$ into a first-order logical formula $Un(M)$ that is provable if and only if $M$ eventually prints 0, Turing proved that Hilbert's Entscheidungsproblem has no solution. By encoding the transition table of any specialized calculating machine as a single string of digits on a universal tape, Turing established the stored-program principle nine years before the first electronic computer was wired.