Turing machines explained
In 1936, before electronic computers existed, the 24-year-old mathematician Alan Turing asked what it means for a calculation to be mechanical. His answer was an imaginary machine so simple that it could hardly do less: it reads and writes symbols on a tape, one cell at a time, by a fixed table of rules. That machine turned out to define computation itself, and it showed that some questions can never be answered by any computer at all.
Turing's question
In 1928 David Hilbert asked whether there is a mechanical procedure that decides, for every statement of mathematics, whether it can be proved: the Entscheidungsproblem. To answer it, someone had to say exactly what a mechanical procedure is. In his 1936 paper On Computable Numbers, Turing imagined a clerk working with pencil and paper, and stripped the work down to its smallest steps: look at one symbol, change it, move to a neighbouring symbol, and remember a little about what you were doing. The result was the Turing machine.
The machine
A Turing machine has a tape divided into cells, endless in both directions, each holding one symbol, usually blank. A head sits on one cell and the machine is in one of finitely many states. A table of rules gives, for each state and each symbol the head can read, the symbol to write, the direction to move and the next state. The machine applies one rule per step. When it enters a halting state it stops, and whatever is left on the tape is its answer.
Programs as rule tables
Each rule table is a program. To add 1 to a binary number, the machine walks to the right end of the number, then moves left turning 1s into 0s until it finds a 0 or a blank, which it turns into a 1. To check whether a word is a palindrome, it erases the first symbol, remembers it in its state, runs to the other end and checks that the last symbol matches, then repeats. Long programs, such as one that multiplies or sorts, are built from the same few kinds of rules.
The universal machine
Turing's most important idea was that the rule table itself can be written on the tape. A universal Turing machine reads a description of any other machine and its input, and then imitates it step by step. One fixed machine can therefore run every program: this is the principle behind every stored-program computer, where software is just data in memory. Any system that can imitate a universal Turing machine is called Turing complete, including every programming language, Conway's Game of Life and the cellular automaton Rule 110.
The Church–Turing thesis
In the same year, Alonzo Church described computation with his lambda calculus, and the two definitions turned out to compute exactly the same functions. So did every later model, from register machines to modern processors. The Church–Turing thesis states that anything that can be computed by a step-by-step procedure can be computed by a Turing machine. It cannot be proved, because "step-by-step procedure" is an informal idea, but no counterexample has ever been found.
The halting problem
Turing then showed that some questions have no mechanical answer. Suppose a machine could decide, for every program and input, whether that program eventually halts. Build a new program that asks this decider about itself and then does the opposite: if it is told it halts, it loops forever, and if it is told it loops, it halts. Either answer is wrong, so the decider cannot exist. The halting problem is undecidable, and with it the Entscheidungsproblem: no algorithm can settle every mathematical question.
Busy beavers
In 1962 Tibor Radó turned the halting problem into a game: among all machines with n states and the symbols 0 and 1 that halt when started on a blank tape, which one writes the most 1s, and how many steps can such a machine take? These numbers, the busy beaver values, grow faster than any computable function, because a way to calculate them would solve the halting problem. The known values are 6, 21 and 107 steps for two, three and four states; for five states the champion of Heiner Marxen and Jürgen Buntrock takes 47,176,870 steps, a value proved in 2024 by the online bbchallenge collaboration with a computer-checked proof. For six states, machines are known that run for more steps than can be written down in ordinary notation.
Explore it
Open the Turing machine simulator to run eight ready-made programs or write your own. Follow the head step by step and see which rule fires, watch the counter that never halts, check palindromes, and run the busy beavers: the four-state champion's 107 steps fit in the diagram, and the five-state champion's 47 million steps take a few seconds at the fastest speed.
Frequently asked questions
Was the Turing machine ever built?
Not as Turing described it, since its tape is endless, but the idea was soon followed by real stored-program computers, which Turing himself helped design after the Second World War. Hobbyists have since built working models from wood, LEGO and even the Game of Life, all with a finite tape, which is enough for any calculation that finishes.
What is the difference between the step counts 14 and 21 for three states?
There are two busy beaver questions: the most 1s written and the most steps taken. For three states, the machine in the simulator writes the maximum of six 1s in 14 steps, while a different three-state machine takes the maximum of 21 steps but leaves only five 1s. For two, four and five states, one machine wins both.
Does Turing complete mean powerful?
It means able to compute anything computable, given enough time and memory, which says nothing about speed. A Turing machine needs many steps for simple arithmetic, and some systems are Turing complete almost by accident, such as card games, spreadsheet formulas and Minecraft redstone.
Why can't a computer just run a program to see if it halts?
Running it shows that a program halts, if it does, but if it has not halted yet you cannot tell whether it never will or just needs more time. Turing's proof shows that no cleverer method works for every program, although for many particular programs the question can be answered.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Open the Turing machine simulator