Turing Complete — a Turing machine you can watch, and the CPU inside it

What a Turing machine actually is

Alan Turing invented this device in 1936, in a paper about the foundations of mathematics — On Computable Numbers, with an Application to the Entscheidungsproblem. He was not designing a computer. He was trying to pin down what it means for a human to follow a procedure by rote, so he could prove that some questions have no procedure at all. So he stripped the idea of "calculating" down until nothing removable was left:

The tape

An unbounded strip divided into squares, each holding one symbol from a finite alphabet. It is the only storage. It plays the role of RAM, disk, and screen all at once — input arrives written on it, and output is whatever is left on it at the end.

The head

Sits over exactly one square. It can read that square, overwrite it, and move one square left or right. It cannot jump, cannot see its neighbours, and cannot remember what it read a moment ago.

The state

One label from a finite set — SCAN, CARRY, A. This is the machine's whole internal memory. Everything it "knows" that isn't written on the tape has to fit in this one label.

The table

A finite list of rules of the form: if the state is q and the square holds s, then write s′, move left or right, and switch to state q′. The table never changes while the machine runs. The table is the program.

Formally a machine is a 7-tuple (Q, Σ, Γ, δ, q₀, ␣, F): a finite set of states Q, an input alphabet Σ inside a tape alphabet Γ, a transition function δ : Q × Γ → Q × Γ × {L, R}, a start state q₀, a blank symbol ␣, and a set of final states F. The machines on this page also allow a "stay put" move, a convenience that adds no power — you can always replace it with a right move followed by a left move.

Machines answer in one of two ways, and it is worth knowing which you are watching. Some leave the answer written on the tape: the arithmetic programs overwrite their input with the result, and you read it off the squares once the machine stops. Others answer by where they stop. A machine of that kind has two distinguished halting states, and which one it reaches is the whole output — accept or reject, one bit, delivered by the state register rather than by anything on the tape. The two recognizer programs in the picker work this way. The distinction matters more than it looks: the question of what is decidable, which the last section is about, is defined entirely in terms of machines of the second kind.

The load-bearing detail is the mismatch between the two halves: the table and the state set are finite and fixed, while the tape is unbounded. A finite controller steering unlimited storage is exactly the shape of a computer, and it is why one fixed CPU design can run programs whose data it was never sized for.

The four beats of the animation

Each transition in the 3D view is split into four beats. They are not part of Turing's definition — his machine just takes one atomic step — but they line up exactly with the cycle a real processor runs, which is the point.

FETCH

Turing machine: the head lowers and reads the symbol under it.

CPU: put an address on the bus, read the word back. The head's position is the address register.
DECODE

Turing machine: find the row of the table matching (state, symbol). Exactly one row can match, so there is no ambiguity — the machine is deterministic.

CPU: the control unit decodes the opcode into the control signals that will drive the next beat. Same lookup, done in gates or microcode.
EXECUTE

Turing machine: write the new symbol into the current square.

CPU: execute and write back — the result goes to a register or to memory.
ADVANCE

Turing machine: move the head one square, and switch to the next state.

CPU: update the address register and advance the program counter. A rule that sends you to a different state is a jump; a rule that depends on the symbol you read is a conditional branch.

Watch the Binary increment program with this in mind. It walks right to the last bit, then flips 1s to 0s leftward until it finds a 0 or a blank to turn into a 1. That is a ripple-carry adder, executed serially. Your CPU does the same computation with the same logic, except the carries propagate through silicon in parallel and the whole thing finishes inside one clock tick.

Binary addition takes it further: a full ADD with carry between two operands. It is worth watching for one detail — the lowercase a and b it leaves behind. Those are result bits the machine has already accounted for, and it has to write that bookkeeping onto the tape because it has nowhere else to put it. A CPU keeps the equivalent in a register.

Now compare both of those with Unary addition and Unary multiplication, which write a number n as a run of n ones. In unary the addition is almost embarrassingly easy — overwrite the plus sign and delete one 1, five rules, eight steps — where the binary adder needs thirty-three rules for the same sum. The arithmetic did not get easier; the encoding did. What unary buys in short programs it pays for in tape: the number one thousand takes ten squares in binary and a thousand of them in unary, so every walk from one end of the number to the other costs proportionally more. Choosing a representation is choosing which costs to pay, which is the same trade you make every time you pick a data structure.

Why a CPU is this machine with better wiring

The correspondence is not a loose metaphor. It is an engineering translation, and it goes both ways: you can compile a real instruction set into a Turing machine table, and you can write a Turing machine simulator in any real instruction set — the one running this page is a few hundred lines of JavaScript.

Turing machine	CPU / computer	Notes
the tape	RAM — the address space	Linear, addressable, read/write, and the only place results can persist.
one square	one addressable word	A TM square holds one symbol; a word holds 64 bits. Just a wider alphabet.
head position	the memory address register	The number currently on the address bus.
move L / move R	`ptr--` / `ptr++`	Address arithmetic. The TM is limited to ±1 per step.
the tape alphabet	the encoding of a word	Symbols are bit patterns. Two symbols is enough for anything.
the current state	program counter + status flags + registers	Everything the machine holds outside memory. Finite, and small.
the transition table	the instruction set, as built into the control unit or microcode ROM	Fixed at manufacture. Wired in, not stored on the tape.
one row of the table	one instruction	Condition → operation → where to go next.
one transition	one clock cycle	Fetch, decode, execute, write back, advance.
a rule whose `next` state differs	`jmp`	Unconditional control transfer.
two rules for the same state, different symbols	`if` / conditional branch	The only way a TM makes a decision: on the symbol it just read.
entering a final state	`hlt`	The machine stops; whatever is on the tape is the answer.
tape + head + state ("configuration")	a core dump: memory image plus register file	Enough to resume the machine exactly. This is what VM snapshots save.
a universal Turing machine	a stored-program computer	The idea that makes your laptop general-purpose. See below.

Program as data: the universal machine

A single Turing machine, with its fixed table, does exactly one job. The move that turns this from a proof device into a blueprint for the entire industry is Turing's next one: build a machine U whose input tape holds a written description of some other machine M, followed by M's input. U reads the description of M's table off the tape and imitates it, step by step, using more tape as its scratch space.

That is a universal Turing machine, and it is one machine that can behave like any machine. Programs and data stop being different kinds of thing: a program is just symbols on a tape that some other machine chooses to interpret as rules.

Your CPU is a physical universal machine. The fixed table is the instruction set, etched into the silicon and identical in every chip of that model. The program lives in RAM alongside its data — one memory, holding both, which is what "von Neumann architecture" names and what distinguishes a computer from a calculator. Every layer above works the same way, all the way up: the JavaScript engine running this animation is a program that treats other programs as data, which is a universal machine implemented on top of a universal machine.

Turing published this in 1936, nine years before there was any electronic computer to run it on. The hardware caught up to the theory, not the other way around.

Where the analogy is exact, and where it leaks

Exact

Same computational power. Anything your CPU can compute, a Turing machine can compute, and vice versa. This is a proved equivalence, not an aspiration. The Church–Turing thesis is the broader claim that this class — the "computable" functions — is the same one you get from lambda calculus, recursive functions, cellular automata, or any other reasonable model anyone has proposed in ninety years. Nothing has ever escaped it.
Finite control, unbounded storage. Both machines have a controller whose size does not grow with the problem, steering memory that does.
Deterministic step function. Both are a rule that maps one complete configuration to the next, with no room for interpretation.

Leaky

Random access. A CPU reaches address 4 billion as fast as address 0. The head has to walk there, one square per step. This costs real time — it can turn a linear-time algorithm quadratic — but it is only a polynomial slowdown, so it never changes what is computable, only how long it takes. This is exactly why complexity theory has to name its machine model and computability theory does not. The Palindrome check program is this tax made visible: it erases the outermost pair of symbols, then walks the entire remaining string to reach the other end, over and over. Quadratic time for a problem a CPU solves in linear time with two pointers.
Finite memory. Your RAM does not grow on demand, so a real computer is strictly a finite-state machine, not a Turing machine. But with 16 GB of RAM the number of possible states is around 2^10¹¹, which makes the finite-state description true and useless. The Turing model predicts real behaviour better than the pedantically correct one.
Registers, caches, pipelines, SIMD, many cores. All of it is speed. Every one of these can be simulated by the single-tape machine with at most polynomial overhead, so none of them lets a computer compute anything new. Parallelism included: four cores do not expand the set of computable functions. Copy a string shows what their absence costs: with only the state register to hold anything, the machine ferries one bit per round trip across the whole tape.
No ALU. A Turing machine has no adder. Arithmetic has to be spelled out in the table, one carry at a time — which is what the increment program above is doing. A CPU hardwires the common operations. That is convenience and speed, not capability.
No input after the start. The classic machine is sealed: its input is on the tape before it begins, and it does not react to anything. Real computers are interactive and interrupt-driven, which needs an extended model to describe properly.

The limits it was invented to prove

Turing built this machine in order to show something couldn't be done. Feed a universal machine a description of a machine and an input, and ask: will it ever stop? There is no Turing machine that answers correctly for every case. The halting problem is undecidable, and the proof is short: if a perfect halting detector existed, you could wrap it in a machine that halts exactly when the detector says it loops, then feed that machine its own description. The contradiction kills the detector.

That is not a curiosity about tape and squares — it is a hard ceiling on real tools. No debugger can flag every infinite loop, no analyser can decide whether arbitrary code is malicious, and by Rice's theorem every non-trivial question about what a program does (as opposed to what it looks like) is undecidable in general. This is why static analysers approximate, why type systems reject some correct programs, and why timeouts exist.

The 3-state busy beaver program in the picker is that ceiling at a size you can watch. Among all three-state, two-symbol machines started on a blank tape, the ones that halt at all take at most 21 steps — and the one loaded here takes exactly 21. That figure comes from checking every such machine by brute force, which is the only known way to get it. The values grow out of all proportion to the machine size: 6 steps for two states, 21 for three, 107 for four, then 47,176,870 for five, a number only pinned down in 2024. For six states, the best lower bounds are written as towers of exponents, and for some machine size in the hundreds the answer is independent of the axioms of set theory — no proof from ZFC can tell you what it is. A twenty-one step program is easy. Knowing what a program will do, in general, is impossible.

So what does "Turing complete" mean?

A system is Turing complete if it can simulate any Turing machine — which, by the equivalences above, means it can compute anything computable at all. It is a surprisingly low bar. You need conditional branching, and you need unbounded storage you can address; almost anything with those two properties clears it. Every general-purpose programming language qualifies, and so do a great many systems that nobody designed to:

Conway's Game of Life, and many other cellular automata.
The x86 mov instruction, on its own, with no arithmetic or jumps.
Spreadsheet formulas, C++ templates, and TypeScript's type system.
Magic: The Gathering, PowerPoint animations, and Minecraft redstone.

This is usually a warning rather than a feature. If your configuration format is accidentally Turing complete, then by Rice's theorem you can no longer decide anything general about what a config file will do — you have shipped a programming language without meaning to. The flip side is the reassuring part: the machine on this page, with four rules and a paper tape, is not a simplified model of your computer. In everything except speed, it is the same machine.

Glossary

This page moves between three vocabularies — the parts of the machine, the parts of a processor, and the theory that connects them. Terms are tagged machine hardware theory accordingly.

Accept / reject machine: Halting states that encode a yes-or-no answer, rather than leaving a result written on the tape. Used by the two recognizer programs.
Address hardware: The number identifying which word of memory to read or write. The head's position on the tape is the exact equivalent.
Alphabet machine: The finite set of symbols allowed on the tape. The tape alphabet includes the blank and any working symbols the machine writes for itself; the input alphabet is the subset your input may use.
ALU hardware: Arithmetic logic unit — the circuit that adds, subtracts and performs bitwise operations in hardware. A Turing machine has none, so arithmetic has to be spelled out rule by rule.
Blank (␣) machine: The symbol occupying every cell that has never been written. There are infinitely many of them in both directions.
Busy beaver theory: Among all n-state machines that halt on a blank tape, the most steps any of them takes — written S(n) — or the most 1s any leaves behind, written Σ(n). The sequence grows faster than any computable function.
Carry / borrow hardware: The bit passed to the next column when a digit overflows during addition, or goes below zero during subtraction. The increment and subtraction programs let you watch one ripple.
Cell machine: One square of the tape, holding exactly one symbol. Equivalent to one addressable word of memory.
Church–Turing thesis theory: The claim that every reasonable model of mechanical computation anyone has proposed — Turing machines, lambda calculus, recursive functions, cellular automata — defines the same class of computable functions. Not a theorem; nothing has ever escaped it.
Clock cycle hardware: One tick of a processor, in which it fetches, decodes, executes and advances. One transition of a Turing machine.
Computable theory: A function is computable if some Turing machine produces its output for every input in a finite number of steps. Everything a computer can ever do.
Configuration machine: A complete snapshot of a run: tape contents, head position, and current state. Enough to resume exactly — the theoretical version of a core dump.
Control unit hardware: The part of a CPU that decodes an instruction into the signals driving the rest of the chip. It is the transition table, built out of gates.
Decidable / undecidable theory: A yes-or-no question is decidable if some machine always halts with the correct answer. If no such machine can exist, the question is undecidable — not merely hard, but impossible.
Deterministic machine: At most one rule matches any (state, symbol) pair, so the next step is never ambiguous. Every machine on this page is deterministic.
Fetch–decode–execute hardware: The cycle a processor repeats forever: read the instruction, work out what it means, carry it out, move on. The four beats in the animation.
Finite-state machine theory: A machine with states but no unbounded storage. A real computer with fixed RAM is technically one of these — true, and useless as a description.
Flags / status register hardware: Bits recording facts about the last operation: zero, negative, carry, parity. The Turing machine equivalent is simply which state it is in — see the parity and subtraction programs.
Halt state machine: A state with no outgoing rules. Reaching one ends the run, and whatever is on the tape is the output. The hlt instruction.
Halting problem theory: Given a program and an input, decide whether it will ever stop. Turing proved in 1936 that no program can answer this for all cases.
Head machine: The mechanism sitting over one cell that reads it, overwrites it, and moves one cell left or right. It is the address register and the data bus in one part.
Instruction set (ISA) hardware: The fixed repertoire of operations a processor implements, decided at manufacture. The transition table.
Microcode hardware: A layer of simpler internal operations used to implement complicated instructions inside the CPU. Early processors implemented multiplication this way, as a loop of additions.
Program counter hardware: The register holding the address of the next instruction. Part of what the Turing machine's single state label stands in for.
RAM hardware: Random-access memory: any address reachable in roughly constant time. The tape, minus the walking.
Register hardware: Small, fast storage inside the processor, separate from memory. A Turing machine has none, which is why several programs here write their bookkeeping onto the tape.
Rice's theorem theory: Every non-trivial question about what a program computes — as opposed to what its text looks like — is undecidable. The reason static analysis approximates.
Rule / transition machine: One row of the table: in this state, reading this symbol, write that, move, and go to that state. One instruction.
State machine: The machine's entire internal memory outside the tape: one label from a finite set. Everything it knows that isn't written down has to fit here.
Tape machine: The unbounded strip of cells that is the machine's only storage. Input arrives on it and output is left on it.
Transition function (δ) machine: The mapping from (state, symbol) to (symbol to write, direction to move, next state). Finite, fixed before the run, and the whole program.
Turing complete theory: Able to simulate any Turing machine, and therefore able to compute anything computable. Requires only conditional branching and unbounded addressable storage — a low bar many systems clear by accident.
Unary theory: Writing the number n as n ones. Trivial for a machine to add and multiply, but exponentially longer than binary — which is why binary arithmetic needs so many more rules here.
Universal Turing machine theory: A machine that reads a description of another machine off its own tape and imitates it. The moment programs became data, and the blueprint for every general-purpose computer.
von Neumann architecture hardware: Instructions and data held in the same memory, so a program can be loaded like any other data. The physical realisation of a universal machine.
Working symbol machine: A symbol in the tape alphabet but not the input alphabet, written by the machine to mark its own progress — the X, Y, a and b you see appear. Notes it keeps for itself, for want of registers.