In 1936 there was no computer. The English word computer meant a person who did calculations for a living, with pencil and paper, in insurance offices, observatories and government departments. Turing started from that person. He asked what they really do when they calculate and stripped away everything that is not essential.

What is left of someone calculating

Turing’s reasoning, in the paper “On computable numbers”, is almost a list of simplifications:

  • The paper can be replaced by a tape divided into squares, because a calculation on squared paper can be copied, square by square, onto a single line.
  • Each square holds one symbol from a finite list: digits, letters, a blank.
  • The person calculating looks at a few squares at a time. Looking at one is enough: looking at several is looking at one, then at its neighbour.
  • The person calculating has a state of mind, such as “I am adding” or “I am carrying one”. There are finitely many such states.
  • Each step depends only on the current state and the symbol being read. The step consists of writing a symbol, moving one square left or right and changing state.

What is left is a machine: a tape, a head that reads and writes, and a table of rules. Each row of the table says: “in such a state, reading such a symbol, write this, move there and go into such a state”.

A machine that adds 1

Let us build a machine that adds 1 to a number written in binary. By hand, the sum $1011+1$ is done from right to left: the last 1 becomes 0 and “carry one”; the second-to-last 1 also becomes 0 and carries one; the next 0 becomes 1, and the sum is done. The result is $1100$, that is, $11+1=12$.

The machine does exactly that, with a single state, “add”, plus the final state “halt”. The head starts on the last digit:

State Reads Writes Moves Next state
add 1 0 left add
add 0 1 stays halt
add blank 1 stays halt

The first row is the carry: it turns 1 into 0 and keeps going left. The second ends the sum when it finds a 0. The third deals with the case where all the digits were 1, as in $111+1=1000$: the head reaches the blank to the left of the number and writes the new 1 there.

Why so poor?

The Turing machine looks ridiculously limited. It cannot add two numbers at once, it has no memory apart from the tape, it moves one square at a time. But this poverty is deliberate. Turing wanted a definition of “mechanical calculation” so simple that nobody could doubt a person carries it out, and at the same time so general that it covered any calculation.

The second half of that bet is known as the Church–Turing thesis: anything that can be calculated by a mechanical procedure can be calculated by a Turing machine. It is not a theorem, because “mechanical procedure” was not a mathematical concept before Turing. It is a thesis that has never been contradicted: every computer built since, from the simplest to the fastest, calculates exactly the same functions as Turing machines, only faster.

Exercise: follow the machine on 111

Start with the tape $111$ and the head on the last 1. Step 1: reads 1, writes 0, moves left; the tape is $110$. Step 2: reads 1, writes 0, left; tape $100$. Step 3: reads 1, writes 0, left; tape $000$, and the head is on the blank before the number. Step 4: reads blank, writes 1 and halts. The tape is $1000$: $7+1=8$, in 4 steps.

Exercise: how many steps?

How many steps does the machine take to add 1 to a number whose last $k$ digits are 1 and the one before is 0?

The $k$ ones become zeros, one step each, and one more step turns the 0 into a 1. That is $k+1$ steps. For even numbers, which end in 0, one step is enough. The worst case is a number made only of ones, with $n$ digits: $n+1$ steps.

Sources: Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society (1936) · Charles Petzold, The Annotated Turing (2008).

All topics on Alan Turing · ← The life of Alan Turing · The halting problem: the question no machine can answer →

Image credits.