A Turing machine.

Step 1 of 5

Read, write, move

In 1936, before there was a single computer in the world, Alan Turing asked what exactly “to compute” means. His answer is an imaginary machine, as simple as it can be, and it stands on a bench in the Scene:

• A long paper tape, divided into cells. Each cell holds one symbol, or nothing.
• A head that stands over one cell, reads the symbol in it, can stamp a new one, and moves one cell left or right.
• A state: one letter on the display on the head. That is all the machine remembers, apart from the tape.
• The rule card, behind the head: a row for each state, a column for each symbol, and a rule in each square.

The processor in the previous Unit went round a loop of fetch, decode and execute. A Turing machine goes round an even simpler one.

Step 2 of 5

Filling the gap

Program is set to Adder. The tape reads 111_11: three and two in tally strokes, where a number is a count of 1s, with a blank between them. The lit rule on the card is the one the machine will use on its next step.

In state A the machine runs right over the 1s and leaves them as they are. After three steps it reaches the gap.

Step 3 of 5

The answer on the tape

After the gap is filled, B runs right to the blank at the end, steps back one and goes to C. C rubs out one 1 and goes to halt: the halting state has no row on the card, so there is nothing more to do. What is written on the tape when it halts is the answer.

Step 4 of 5

Counting steps

As with the processor, you can ask how much work the machine does: how many steps until it halts. Follow in your head what each state does.

Step 5 of 5

The third state

Steps run is free now. Move it one step at a time, and watch the lit rule and the letter on the display.