The Turing Machine: A Simple Model of All Computation

Five parts, and nothing else

Alan Turing's 1936 paper described the simplest possible model of a calculating machine, and it turned out to be powerful enough to define what "computable" even means. A Turing machine has an infinite tape divided into cells, each holding a symbol from a finite alphabet; a head that reads and writes one cell at a time and can move left or right; a finite set of internal states; and a transition table that says, for each (state, symbol) pair, which symbol to write, which way to move, and which state to enter next.

transition rule:  (state, read) → (write, move, next_state)

example — binary increment, rightmost bit first:
(scan, 0) → (0, RIGHT, scan)
(scan, 1) → (1, RIGHT, scan)
(scan, _) → (_, LEFT,  carry)
(carry,1) → (0, LEFT,  carry)
(carry,0) → (1, LEFT,  halt)

Why something this simple can compute anything

The machine has no built-in arithmetic, no memory beyond the tape, and no notion of numbers, loops or variables — those all have to be encoded as symbols and states. Yet Turing showed that this bare mechanism can simulate any other Turing machine given a description of it on the tape (the universal Turing machine), and church and Turing independently argued that anything a human following an algorithm could compute, a Turing machine could compute too — the Church–Turing thesis. No stronger model of computation has ever been found; every general-purpose programming language, no matter how different it looks, is provably equivalent in what it can compute.

The halting problem

Turing's paper is really about a negative result. He proved that no algorithm can decide, for every possible machine and input, whether that machine will eventually halt or run forever. The proof is a diagonal argument: assume a halting-decider H exists, then build a machine that asks H about itself and does the opposite of whatever H predicts — a contradiction, so H cannot exist. This single result underlies why compilers cannot always detect infinite loops, why some program-verification questions are provably unsolvable, and why the Game of Life's long-term behaviour is undecidable in general (it can simulate a Turing machine).

Busy beavers: the price of simplicity

If you restrict a Turing machine to a tiny number of states, how much can it still do before it halts? The busy beaver function BB(n) asks for the maximum number of steps (or 1s written) that an n-state, 2-symbol machine can produce before halting, among all machines that do halt. BB(1)=1, BB(2)=6, BB(3)=21, BB(4)=107 are known exactly; BB(5) was only pinned down in 2024, after decades of search, at 47,176,870 steps. Beyond that the function grows faster than any computable function — computing it exactly is equivalent to solving the halting problem, so BB(n) is itself formally uncomputable for large enough n. A handful of extra states buys an almost unbounded amount of possible behaviour.

What the simulator on this site runs

The five built-in programs are all small, hand-designed transition tables: binary increment (carry propagation across bits, shown above), unary addition (merging two runs of marks into one), a palindrome checker (walking inward from both ends of the tape and comparing symbols), string copy (shuttling a marker back and forth to duplicate a block), and the 3-state busy beaver, which despite only three states and two symbols manages to write six 1s before halting — the maximal such machine, proved optimal by exhaustive search decades ago.

Frequently asked questions

Try it live

Everything above runs in your browser — open Turing Machine and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.