Alan Turing: thinking about what computers can do
Alan Turing (1912–1954) was a mathematician whose work helped shape computer science. In 1936 he developed a mathematical description of computation. During the Second World War he worked with the codebreaking team at Bletchley Park; afterwards he worked on computers at the National Physical Laboratory and Manchester. His work also explored patterns in living things. Read the King’s College biography.
A computer imagined on paper
A Turing machine is a mathematical model with a tape of cells, a reading and writing head, and a finite set of rules. A rule uses the current state and symbol to decide what to write, where to move and which state comes next. The tape has no fixed storage limit. Turing also described a universal machine that can simulate other such machines from their encoded descriptions. See Turing’s original paper, sections 1 and 6.
Try being the machine
Draw a row of boxes containing 1 1 1 _. Let _ mean an empty cell. Put a pencil beneath the first box: it represents the head.
Use this little rule table. The starting state is scan.
| State | Read | Write | Move | Next state |
|---|---|---|---|---|
| scan | 1 | 1 | Right | scan |
| scan | Empty | 1 | Stay | stop |
Follow one row at a time. You should finish with four ones. If the ones stand for a count, your machine has added one.
Try again with five ones followed by an empty cell. Do you need different rules? What happens if your pencil starts on the empty cell instead?
This is one tiny machine with one job. It is not itself a universal machine.
Connect it to Pliro
When you trace a Pliro program, you also follow instructions and keep track of changing values. A Turing machine gives us a very stripped-down way to study such steps. You do not need to build one before writing a game.
The next article explains Turing completeness: what it means for a language or model to express general computation.
And the Turing test?
The Turing test concerns whether a machine can imitate human conversation. It grew from Turing’s 1950 discussion of an imitation game. That is a different question from which computations a language can express. See Computing Machinery and Intelligence.