Tool · 2026-08-12
Turing machine, on three programs.
A machine that has, at every moment, a one-way infinite paper tape, a head hovering over one cell of it, and a state written on a card somewhere off to the side. On each tick it reads the cell, and a little table tells it what to write back, which way to shift the head, and which state to switch its card to. That is the whole apparatus. Turing wrote it down in 1936 to argue about what a computable function could and could not be. Here, three programs.
Reading blank on state A
| state | read blank | read 0 | read 1 |
|---|
One step
The machine reads the symbol under the head. It looks up the pair (state, symbol) in its transition table and gets back three things: a symbol to write into that same cell, a direction to shift the head (left or right by one), and the next state. It writes, shifts, switches, and the next step begins. If the pair is not in the table the machine halts. That is the entire operational semantics.
The three programs
The unary increment is the shortest useful program the machine can run. The tape starts with three ones. State A walks right over ones. The moment it reads a blank it writes a one and halts. The count on the tape has gone up by one.
The binary increment starts with 1011 to the right of the head. State A walks to the least significant bit, state B adds one and carries left, state C walks back home. The output is 1100. The carry propagates through as many ones as there happen to be, and the head has to remember where it started, which is what state C is for.
The two-state busy beaver is the champion, discovered by Tibor Rado in 1962, of the game he named: among all halting Turing machines with two states and a binary alphabet, which one runs longest before it halts. The answer is six steps and four ones, and it beats every other two-state program by construction. The three-state champion runs fourteen steps. The five-state number is not known.
On the infinite tape
Twenty-five cells are shown, but the tape is infinite in both directions. Cells you have not visited hold a blank, drawn faint. When the head marches off the visible strip, the view scrolls to keep the head centred, so the cell you are watching is always the one being read. The position readout, positive right and negative left of the start, gives you an absolute reference.
Sources
- Turing, A. M. (1936). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42(1), 230–265. The paper that introduces the machine and uses it to show the halting problem is undecidable.
- Rado, T. (1962). On Non-Computable Functions. Bell System Technical Journal, 41(3), 877–884. The paper that defines the busy beaver game and proves the function is not computable.
- Aaronson, S. (2020). The Busy Beaver Frontier. ACM SIGACT News, 51(3), 32–54. A modern survey of what is known and what is not for BB(n) at small n.