# Alan Turing: thinking about what computers can do

[Concepts explained](README.md)

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](https://turingarchive.kings.cam.ac.uk/about-alan-turing).

## 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](https://theory.stanford.edu/~trevisan/cs172-07/turing36.pdf).

## 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](../guides/tracing.md), 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](turing-completeness.md): 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](https://courses.cs.umbc.edu/undergraduate/471/papers/turing.shtml).

[Algorithms](../guides/algorithms.md) · [Turing completeness](turing-completeness.md)