A Turing machine is a state Q, a tape alphabet Σ = {0,1}, and a transition function
δ: Q × Σ → Q × Σ × {L, R}
At every step it reads the symbol under the head, looks up δ(state, symbol), writes a new symbol, moves the head left or right, and switches state — until it enters HALT, or never does.
The busy beaver function Σ(n) is the largest number of 1s some n-state, 2-symbol machine can leave on the tape before halting; S(n) is the most steps some (possibly different) n-state machine can take before halting. Both are known exactly only for tiny n:
Σ(2)=4, S(2)=6
Σ(3)=6, S(3)=21
Σ(4)=13, S(4)=107
Σ(5)=4098, S(5)=47,176,870 (proved 2024)
The 2-state and 4-state machines below are the actual step- and ones-record holders — run them and the stats panel will land on exactly 6/6 and 107/13. The 3-state machine shown is verified live, on this page, to only need 14 steps to leave the record 6 ones — Σ(3) and S(3) are in general achieved by different machines of the same size, and this is that case: the 21-step title belongs to a different 3-state table than the one demonstrated here, a subtlety the original write-up glossed over.
Why "omnipotent" breaks here. Suppose a "halting oracle" H(M, input) existed that always correctly answers whether machine M halts. Build a machine D that runs H(D, D): if H says "halts", D loops forever; if H says "loops forever", D halts immediately. Either answer H gives is wrong about D — a contradiction. So no algorithm, however powerful, can decide halting for every machine. Try the "Simple non-halter" below: you can watch it run past any step cap you like and never be sure — from observation alone — that it won't halt on step one billion and one.
- Machine select — swap between three provably-optimal busy beavers and a trivial machine that runs forever.
- Run / Step / Step ×10 — animate continuously at the chosen speed, or advance by hand.
- Tape zoom — widen or shrink each cell on the tape strip.
- Camera follows head — auto-centers the tape view on the read/write head; untick it (or just drag) to explore the tape manually.
- State graph — every state is a node; the edge lit up in amber is the transition the machine just took.
- Reset — clears the tape and restarts the selected machine from state A.