What is a Turing Machine?

A Turing machine is the original idealized model of a computer, invented by Alan Turing in 1936.

Turing machines are equivalent to modern electronic computers at a certain theoretical level, but differ in many details.

A Turing machine consists of a line of cells known as the "tape", together with a single active cell, known as the "head". The cells on the tape can have a certain set of possible colors, and the head can be in a certain set of possible states.

Any particular Turing machine is defined by a rule which specifies what the head should do at each step. The rule looks at the state of the head, and the color of the cell that the head is on. Then it specifies what the new state of the head should be, what color the head should "write" onto the tape, and whether the head should move left or right.

The prize Turing machine has two possible states of its head, and three possible colors on its tape.

The animation below shows the operation of the machine, with the states of the head represented by the orientation of the arrows.

In the example shown, the Turing machine starts from a "blank" tape in which every cell is white.

In the analogy with a computer, the "tape" of the Turing machine is the computer memory, idealized to extend infinitely in each direction.

The initial arrangement of colors of cells on the tape corresponds to the input given to the computer. This input can contain both a "program" and "data". The steps of the Turing machine correspond to the running of the computer.

The rules for the Turing machine are analogous to machine-code instructions for the computer. Given particular input, each part of the rule specifies what "operation" the machine should perform.

The remarkable fact is that certain Turing machines are "universal", in the sense that with appropriate input, they can be made to perform any ordinary computation.

Not every Turing machine has this property; many can only behave in very simple ways. In effect, they can only do specific computations; they cannot act as "general-purpose computers".

This prize is about determining how simple the rules for a Turing machine can be, while still allowing the Turing machine to be "universal".

A universal Turing machine has the property that it can emulate any other Turing machine---or indeed any computer or software system. Given rules for the thing to be emulated, there is a way to create initial conditions for the universal Turing machine that will make it do the emulation.

Turing machines are widely used in theoretical computer science for proving abstract theorems. Studying specific Turing machines has been rare. For more information, see the Background to the Prize and the section on Turing machines in A New Kind of Science.