Turing Machines, Explained
After reading this you will be able to read a Turing machine's rule table, trace a computation step by step on paper, and predict what the busy beaver does before you run it.
What a Turing machine actually is
A Turing machine is the smallest honest model of a computer. It has three parts: an infinite tape divided into cells, a head that sits over one cell and can read or write a single symbol, and a state that records where the machine is in its own logic. A finite table of rules tells the head what to do next.
That is the whole machine. No memory addresses, no registers, no arithmetic unit. Yet this device can compute anything your phone can compute, given enough tape and time. Alan Turing proved this in 1936, before any physical computer existed.
Here is the hook. The 3-state busy beaver starts on a blank tape, all zeros. It halts after exactly 14 steps, and when it stops the tape holds six 1s. No 3-state machine that halts can write more. That single number, 6, is a famous constant in computability theory, and you can watch the machine reach it one step at a time.
When this model helps, and when it does not
Reach for a Turing machine when you want to understand what computation is, not to compute anything quickly. The model exists to answer questions like "is this problem solvable at all?" and "how much work does a solvable problem require in the worst case?"
It is a terrible tool for real calculation. Incrementing the binary number 101 to 110 takes a Turing machine several head moves and state changes. Your CPU does it in one instruction. The point of the model is honesty, not speed: every operation is broken into atoms so nothing hides.
The Church-Turing thesis says that any function a human could compute by following a fixed procedure can be computed by a Turing machine. It is not a theorem, it is a claim about what "computable" means. Eighty years of trying to find a counterexample have failed.
The transition rule, symbol by symbol
The entire behavior of the machine lives in its transition function. Given the current state and the symbol under the head, the function returns three things: a symbol to write, a direction to move, and the next state.
Here q is the current state, s is the symbol read from the tape, s' is the symbol written back into that same cell, d is the move (L for left, R for right), and q' is the state the machine enters next. One special state, q_{halt}, has no outgoing rules; reaching it stops the machine.
A machine over a two-symbol alphabet with n states has at most 2n rules, one for each (state, symbol) pair. The 3-state busy beaver uses states A, B, C plus halt, so its table has 3 \times 2 = 6 rules. That is the complete program.
A worked example: the 3-state busy beaver
Run the simulator with its default machine and you get the busy beaver below. The tape starts blank (all 0), the head sits at position 0, and the machine begins in state A.
| State | Read | Write | Move | Next |
|---|---|---|---|---|
| A | 0 | 1 | R | B |
| A | 1 | 1 | L | C |
| B | 0 | 1 | L | A |
| B | 1 | 1 | R | B |
| C | 0 | 1 | L | B |
| C | 1 | 1 | R | halt |
Tracing all 14 steps
Read each line as: the state and read symbol on the left pick a rule, then the head writes, moves, and switches state. The position column is the cell the head lands on after the move.
- State A, pos 0, reads 0. Write 1, move R, go to B. Tape:
1at 0. - State B, pos 1, reads 0. Write 1, move L, go to A. Tape: 1s at 0,1.
- State A, pos 0, reads 1. Write 1, move L, go to C. Head now at -1.
- State C, pos -1, reads 0. Write 1, move L, go to B. Head at -2. Tape 1s at -1,0,1.
- State B, pos -2, reads 0. Write 1, move L, go to A. Head at -3.
- State A, pos -3, reads 0. Write 1, move R, go to B. Head at -2.
- State B, pos -2, reads 1. Write 1, move R, go to B. Head at -1.
- State B, pos -1, reads 1. Write 1, move R, go to B. Head at 0.
- State B, pos 0, reads 1. Write 1, move R, go to B. Head at 1.
- State B, pos 1, reads 1. Write 1, move R, go to B. Head at 2.
- State B, pos 2, reads 0. Write 1, move L, go to A. Head at 1.
- State A, pos 1, reads 1. Write 1, move L, go to C. Head at 0.
- State C, pos 0, reads 1. Write 1, move R, go to halt.
- Halt. Count the 1s: cells -3, -2, -1, 0, 1, 2. That is six 1s.
Notice step 13 is the only rule that leads to halt, and it fires exactly once. Every other step keeps the machine alive. The 1s end up contiguous from cell -3 to cell 2, six cells wide.
Reading the animation
Three things move together in the simulator, and each tells you something different.
- Head position
- Where the read and write happen this step. Watch it to see whether the machine is scanning outward, sweeping back, or oscillating in place.
- Current state
- The machine's short-term memory. A machine with three states can remember at most three distinct situations, so state changes are the logic branching.
- Highlighted rule
- The single table row that fired. If you pause and match the highlighted row to the head's cell and the current state, the (state, read) pair on the left must equal what you see on the tape and in the state badge.
A halted machine is not a crashed machine. Halting is success: it means the computation finished and the tape holds the answer. A machine that never reaches a halt rule runs forever, and there is no general procedure to tell in advance which machines do that. That undecidable question is the halting problem.
Common mistakes when reading or building machines
The first trap is confusing state with position. State C does not mean "cell number 3." State is abstract memory; position is a physical location on the tape. In the busy beaver, state B occurs while the head sits at positions 1, -2, -1, 0, 1, 2 across the run. The state repeats; the position does not.
Do not assume a machine halts just because it looks busy. A one-line change to the busy beaver table, sending state C back to B on read 1 instead of to halt, produces a machine that never stops. Small tables can loop forever, and staring at the animation will not prove either outcome. Only a finished halt tells you it terminates.
The second trap is the blank symbol. The tape is infinite and filled with 0 in both directions. When the head steps onto fresh tape it reads 0, so you must include a rule for reading 0 in every state the machine might reach there. Omit one and the machine has no rule to follow, which is a different kind of stop from a real halt.
The third trap is off-by-one counting of steps. A "step" is one rule application: read, write, move, change state, all at once. Step 14 in the trace above is the halt itself, so the machine executes 13 rewriting steps and the answer is six 1s. The busy beaver score counts the six 1s, not the steps.
Related tools on this site
A Turing machine is the most general model of computation, and the machines below are its restricted, practical cousins. If you want to see the boundary between finite and infinite memory, the Regex to Automaton tool builds a finite automaton, a Turing machine with no writing and only forward moves. To watch concrete algorithms that a Turing machine could in principle run, try the Sorting Algorithm Visualizer or the Pathfinding Visualizer. For the cost side of computation, the Big-O Complexity Race shows how step counts grow, and the Dynamic Programming Visualizer fills tables the way a well-designed tape would.
Frequently asked questions
Why is it called a busy beaver?
The name comes from a machine that stays as "busy" as possible, writing the most 1s it can before halting, given a fixed number of states. The 3-state, 2-symbol champion writes six 1s in 14 steps. The 4-state champion writes 13 1s. The 5-state and 6-state numbers grow so fast that they cannot be computed by any general method.
Is a real computer a Turing machine?
Almost. A real computer has finite memory, so it is technically a large finite automaton. But any computation that fits in its memory is one a Turing machine can also do, and the Turing model captures every algorithm your computer can run given more storage.
Can every Turing machine be simulated by another?
Yes. A single fixed machine, called a universal Turing machine, can read a description of any other machine plus its input from the tape and simulate it exactly. That is the theoretical basis for the idea that one general-purpose computer can run any program.
Why does the busy beaver reach six 1s before it halts?
The sixth 1 is written at step 11, but the halting rule only fires when the machine is in state C reading a 1. After step 11 the head must sweep back left to reach a cell containing a 1 while in state C, which takes two more steps. The 1 count is finished; the positioning is not.
What is the difference between halting and getting stuck?
Halting means the machine reached a defined halt state through a rule that sent it there. Getting stuck means it reached a (state, symbol) pair with no matching rule. Both stop the machine, but a well-formed machine should always have a rule for every reachable pair and halt deliberately.
Related tools
Dynamic Programming Visualizer
Watch edit distance and knapsack fill their tables cell by cell — dynamic programming with the lid off.
Graph Algorithm Playground
Build a graph by clicking, then watch BFS, DFS, Dijkstra and Prim explore it live.
Huffman Coding Visualizer
Type any text and watch the optimal prefix code assemble itself as a tree, rare letters sinking deepest.
Pathfinding Visualizer
Draw walls and watch A*, Dijkstra, greedy and breadth-first search hunt for the shortest path.
Sorting Algorithm Visualizer
Watch bubble, insertion, merge, quick and heap sort race through the same shuffled bars.
Hamming Code Playground
Flip any bit of a Hamming-encoded message and watch the parity checks point straight at the culprit.