Turing Machine
An idealized machine of tape, head, and rules that defines exactly what it means for something to be computable.
Turing Machine
A Turing machine is the simplest device powerful enough to compute anything a computer can. Alan Turing dreamed it up in 1936 — years before working hardware — not to build but to define: it pins down, with mathematical precision, what the word computable means. Strip a computer down to its absolute essentials and this is what remains.
The whole machine is just four parts:
- an infinite tape divided into cells, each holding a symbol (say
0,1, or blank); - a head that sits over one cell, able to read and rewrite it;
- a state drawn from a small finite set (the machine's entire "memory" beyond the tape);
- a transition table of rules of the form "in state q reading symbol s: write s', move left or right, go to state q'."
That is the entire universe of the machine. Astonishingly, it is enough.
Watch one run
The machine below is a binary counter. Its head sits at the rightmost bit and runs the schoolbook increment rule: a 1 becomes 0 and the head carries left; the first 0 it meets becomes 1 and the machine halts. Then it counts again. Every sweep of the head to the left is a carry propagating — the same logic in your calculator, laid bare.
Two states (INC, DONE) and a one-line rule produce unbounded counting. Give it more states and a richer table and the same machinery can sort, search, factor, or simulate any other computer.
Why this toy is the whole point
The Turing machine matters precisely because it is so weak-looking. If even this can be made to compute a function, the function is computable; if no Turing machine can, no machine can — that universality is the content of the Church–Turing Thesis. A single universal Turing machine can read another machine's table off its tape and imitate it, which is exactly what a stored-program computer does: code is just data on the tape.
This same definition is what makes impossibility provable. Because computable now has an exact meaning, one can show certain problems have no machine at all — most famously the Halting Problem: no Turing machine can decide whether an arbitrary machine eventually halts. And the local-rule universality on display here is not unique to tapes; a Cellular Automaton such as Conway's Game of Life is Turing-complete from nothing but cells flipping on and off.