Part I · Chapter 1
Moving Symbols
Symbols, a state, and a rulebook that only ever looks at one spot. Nothing more is needed to compute.
A game with a strip of paper
Here is the first rung. Take a long strip of paper divided into squares. Some squares hold a 0, some a 1, and the rest are blank. Put your finger on one square. Keep one word in your head, which we will call your state. To start, the word is CARRY.
Here is the whole rulebook:
| If your state is… | and the square under your finger shows… | then write… | move your finger… | and your new state is… |
|---|---|---|---|---|
| CARRY | 1 | 0 | one square left | CARRY |
| CARRY | 0 | 1 | — | STOP |
| CARRY | blank | 1 | — | STOP |
Now write 1 0 1 1 on the strip and put your finger on the last 1 on the right. Follow the rules:
- State CARRY, you see 1. Write 0, move left. The strip reads 1 0 1 0.
- State CARRY, you see 1. Write 0, move left. The strip reads 1 0 0 0.
- State CARRY, you see 0. Write 1, stop. The strip reads 1 1 0 0.
You started with 1011 and ended with 1100. In binary, 1011 is eleven and 1100 is twelve. You added one.
Figure 1.1. The add-one machine at its first step: a strip of squares, one word held in mind, and a rule.
Try it with 1 1 1. Each 1 becomes 0 as you move left. Then you reach the blank square in front of the number, write a 1, and stop: 1000, which is eight (seven plus one). The third rule exists for exactly this case.
Notice what you did not need. You did not need to know what a number is, or what “adding” means, or that the strip was in binary. You never looked at more than one square. You just matched a pattern in a table and did what it said. The meaning, adding one, belongs to us, the people reading the strip. The process itself is just symbols being moved by rules.
Symbols, state and rules
Every computation, from this toy to the chip in your phone, is built from the same three ingredients.
- Symbols. Marks that can be reliably told apart: 0 and 1, letters, high and low voltages. What matters is that they differ, not what they look like.
- State. A small amount of memory about “where we are in the procedure”. In the toy it was one word: CARRY or STOP.
- Rules. A finite table that says, for each combination of state and symbol in view, what to do next. Every rule is
- local: it sees only the symbol at the current position;
- simple: it is a lookup, not a judgment;
- fixed: the table never changes while the machine runs.
Alan Turing described this device, with a tape as long as needed, in 1936. We call it a Turing machine. Turing was not trying to build a computer. He was trying to capture, as precisely as possible, what a person does when calculating with pencil and paper. Look at a few marks. Recall where you are in the method. Write something. Move on.
A snapshot and a path
Freeze the machine at any instant and write down everything about it: the full contents of the tape, where the finger is, and the current state. Call this a snapshot (the technical word is configuration). The rules turn each snapshot into exactly one next snapshot.
So a computation can be pictured in a second way: as a path through the space of all possible snapshots. That space is enormous. Even our four-square strip, with three symbols per square, four finger positions, and two states, has
This second picture, a path through a space of states, driven by a fixed rule, will come back again and again. It describes a network being trained (Chapter 5) and a language model writing out its reasoning about a sick child (Chapter 11). It is the most important picture in this book.
At this step, the machine is a strip of paper and a finger following a rulebook: it computes, but only while someone moves the finger.