Question
What Is a Turing Machine?
A Turing machine is a simple imaginary device that defines what it means to compute. Alan Turing described it in 1936, and although no one builds one to use, almost every idea in computer science rests on it.
The machine itself is deliberately basic. Picture an endless tape divided into cells, each holding a symbol, and a head that sits over one cell at a time. The head can read the symbol, write a new one, and move left or right, all according to a fixed table of rules. That is the whole machine. There is nothing else to it.
The surprising part is what this simple device can do. Turing showed that a machine like this can carry out any computation that any computer can, no matter how powerful. He also described a universal Turing machine, one that can imitate any other by reading its rules from the tape, which is the idea behind the general-purpose programmable computer.
Because of this, the Turing machine is used as the definition of computation itself. A problem is called computable if a Turing machine can solve it, and questions that no Turing machine can answer, such as the halting problem, mark the limits of what any computer will ever do.
Frequently asked
What is a Turing machine in simple terms?
It is an imaginary machine with an endless tape of cells and a head that reads and writes symbols one at a time, following a set of rules. Despite being so simple, it can carry out any computation that any computer can, which is why it is used to define what computing is.
Did Alan Turing build a Turing machine?
No. The Turing machine is a thought experiment, not a physical device. Turing used it in 1936 to reason about what can and cannot be computed, not to build hardware.
Why is the Turing machine important?
It gives a precise definition of computation. Anything a Turing machine can compute is considered computable, and real computers are judged against it. It is one of the founding ideas of computer science.