In 2024 the Busy Beaver Challenge proved, in the Coq proof assistant, that no five-state two-symbol Turing machine that halts from a blank tape runs longer than 47,176,870 steps. The proof enumerates every machine that matters and hands each one to a decider: a program that either proves it halts, proves it never halts, or gives up. This page explains each decider and runs it in your browser on machines and certificates taken from the proof itself.
Coq-BB5 runs every enumerated machine through the deciders in turn, cheapest first, until one answers. Loops settles almost everything; each later stage handles what the earlier ones could not. The counts below are from the proof's own tally (CoqBB5/BB5/README.md) and the BB(5) paper's Table 2. The bars are on a logarithmic scale, because the stages span seven orders of magnitude.
| Stage | Nonhalting | Halting | Total | In Coq-BB5 |
|---|
The 6,005,142 n-gram CPS machines are 6,003,729 from the generic runs plus 1,413 listed with their own parameters in Decider_NGramCPS_Hardcoded_Parameters.v; RepWL, FAR, WFAR and the long halters are all hardcoded lists. Those lists are embedded in this page, so the batch buttons below rerun the proof's own cases.
All the nonhalting deciders except Loops are instances of the closed tape language (CTL) argument: find a set of configurations that contains the start (blank tape, state A), is closed under one step of the machine, and contains no configuration about to halt. Then the run can never leave the set, so it never halts. The deciders differ in what kind of set they look for: sets of short windows (n-gram CPS), regular expressions with repeated words (RepWL), any regular language given by an automaton (FAR), or a language with a counter (weighted FAR, the only one that is not regular). FAR works the other way round, as "co-CTL": it builds a regular language containing every configuration that will eventually halt and checks that the start is not in it.
A machine is written in the standard text format: one group per state, A first, giving for symbol 0 then symbol 1 the symbol to write, the direction and the next state. --- is the halting transition. The diagrams on this page draw one row per step, time going down: dark cells are 1s, the orange cell is the head.
The default is the BB(5) champion, which halts after 47,176,870 steps with 4,098 ones on the tape.
The simplest way not to halt is to repeat. A cycler returns to exactly the same configuration (state, head position and tape). A translated cycler repeats a configuration shifted along the tape: it walks off one side forever, like a glider, rebuilding the same pattern at its edge. The paper reports that about 86% of the loops it found are translated cyclers.
Coq-BB5's loop1_decider (Deciders/Decider_Loop.v) does not compare tapes at all. It simulates L steps, records the transcript of (state, symbol read, head position) at each step, and looks backwards from the end for a stretch of the transcript that repeats twice back to back. It then rewinds the pair until either the two starting head positions coincide (a cycler) or both starts are at the edge of the visited tape on the side the head is moving to (a translated cycler). The paper proves this is enough: the cells the repetition reads were all written during the repetition itself, or lie in untouched blank tape. Halts seen within the L steps are reported too, which is why this stage also catches 48,379,711 of the 48,379,894 halters.
The pipeline runs it with L = 130, then 4,100, and finally 1,050,000 for two machines listed in Decider_Loop_Hardcoded_Parameters.v.
Each entry is state, symbol read and head position. The decider only needs these; the asterisk marks a step where the head is at the right (or left) edge of the visited tape.
n-gram CPS (Nathan Fenner's simplification of the closed position sets in Skelet's bbfind) forgets everything about the tape except short windows. A local context is the state, the symbol under the head and the n cells on each side, written like 011 [B 0] 100. Two more sets record which n-grams have been seen to the left (L) and right (R) of contexts.
Each context is stepped. If B reading 0 is 1RC, then 011 [B 0] 100 becomes 111 [C 1] 00?: the leftmost cell falls out of view (so 011 joins L), and the unknown cell ? is filled in every way allowed by the n-grams in R that start with 00. The decider repeats this until nothing new appears. If no context in the final set is about to take a halting transition, the machine never halts, since every real configuration's window is in the set.
Coq-BB5 makes this much stronger by enlarging the alphabet: each cell can also remember the last k (state, symbol) pairs that visited it (history), or all of them in order of last use (LRU). The augmented machine behaves exactly like the original, but its windows carry more information. Without augmentation n-gram CPS decides 5,117,863 machines, with history 887,093, and with LRU 182.
Coq-BB5 lists 1,413 machines with the n-gram length and augmentation that decides them. These buttons run the in-page decider on them with those parameters.
RepWL, introduced in Coq-BB5 by mxdys, cuts the tape into words of a fixed length l counted outwards from the head, and writes any word repeated T or more times as (w)^T+, "at least T copies". The configuration 0∞ 11100 A> 111101010111111111 0∞ with l = 2 and T = 3 becomes 0∞ (01) (11) (00) A> (11)^2 (01)^3+ (11)^3+ 0∞. The head sits between cells and points at the word it is about to read.
Two moves explore these regex configurations. Block simulation: when the head faces a word with a fixed count, run the machine inside it until it walks out, then regroup. Regex branching: when it faces (w)^T+, split into "exactly T" and "more than T" and continue both. If the graph of configurations closes with no halt, the machine never halts. This handles the bouncers, machines that sweep back and forth over a growing tape of repeated words.
Each of the 6,577 machines comes with its own (l, T), found by a grid search: l from 1 to 57 and T from 2 to 4, with at most 320 steps per block and 150,001 nodes.
Solid arrows are block simulation, dashed arrows regex branching. Graphs of more than 40 nodes are listed instead of drawn.
The machine's first steps from the blank tape.
Two sets of rules agree on what they prove but count nodes differently. The paper's RepWL figures and its node counts (42, 845 and 143,181 for its three examples, 3,130 and 3,076 for the two four-state machines) come from the Python reproduction in bbchallenge-deciders, which runs a whole (w)^k block at once and keeps blocks of zeros next to 0∞. Coq-BB5 pops one word at a time and lets zero words merge into 0∞. On the 6,577 listed machines the Coq rules decide all of them. The Python rules decide all but three, where a 28-cell word repeated twice needs more than 320 steps when run as one block.
A machine that halts is proved halting by running it. Loops already catches every halt within 4,100 steps; 183 machines halt later and are simply simulated up to 47,176,870 steps (Decider_Halt_BB5.v). The champion found by Heiner Marxen and Jürgen Buntrock in 1989 is the longest: 47,176,870 steps, leaving 4,098 ones. That number is the lower bound of S(5); everything else on this page is the upper bound.
| Machine | Steps to halt | Ones |
|---|
FAR, developed by Justin Blanchard (with implementations by Tony Guilfoyle and Tristan Stérin), looks for a regular language that contains every configuration that will eventually halt, then checks that the blank start is not in it. Configurations are written as words such as 0110C1001: the tape, with the state letter just before the head's cell.
The certificate is a small deterministic automaton (DFA) that reads the tape to the left of the head. From it Coq-BB5's dfa_nfa_verifier (Deciders/Verifier_FAR.v) builds a nondeterministic automaton (NFA). Its states are pairs (DFA state, machine state) plus a sink ⊥, and it reads the head's cell and everything to its right. Its transitions are forced by the machine: a halting transition goes to ⊥, a right move follows the DFA, and left moves are added until nothing changes. By construction the NFA reaches ⊥ on every configuration that will eventually halt. If the start configuration, read on zeros, never reaches ⊥, the machine never halts. Finding the DFA is the hard part: weeks of search for some of the 23. Checking it takes milliseconds.
Machine 1RB0LD_1LC1RA_0RB0LC_---1LA with the two-state DFA that tracks the last symbol read (0 → state 0, 1 → state 1). The NFA below is computed in your browser from the machine and the DFA; it is the one drawn in the paper's Figure 12. The double circle is ⊥, the "will halt" sink; the start state 0A is outlined in blue. A label like 0|1 means the edge is taken on either symbol.
From Verifier_FAR_Hardcoded_Certificates.v: each machine with its DFA.
| Machine | DFA states | NFA states | Result |
|---|
Some machines have no regular invariant at all, typically because they keep two counts in balance. A finite automaton cannot check that 0ⁿ1ⁿ has as many 0s as 1s; a weighted automaton can, by adding +1 for each 0 and −1 for each 1 and accepting total weight zero. Weighted FAR, Iijil's method, is a CTL argument with two deterministic weighted automata. One reads the tape left of the head, left to right, and the other reads the right side, right to left. A configuration becomes [p] C1 [q] with a total weight W.
Coq-BB5's MITM_WDFA_verifier (Deciders/Verifier_WFAR.v) starts from [p0] A0 [q0] with W = 0. It steps the machine abstractly: a right move updates the left automaton with the written symbol and branches over every way the right automaton could have arrived at its state. Weights travel along as exact values or as bounds (W ≥ d, W ≤ d) once they pass a cap. Configurations whose bound contradicts the signs the automata force (for instance, a state every word reaches with weight ≤ 0 alongside W ≥ 2) are thrown out. If the set closes without a halting transition, the machine never halts. The paper believes the 17 machines it decides are irregular, because long searches found no regular proof for them.
Machine 1RB---_0RC1LC_1RD1RC_1LE1LD_0RA0LE, a counter, with the certificate exactly as Coq-BB5 hardcodes it (cap 2). Edge labels are symbol:weight; zero weights are omitted. The right automaton has a third state, a dead sink, which the paper's Figure 13 leaves out.
| Machine | Left / right states | Cap | Closed set | Result |
|---|
Thirteen machines resisted every decider and were proved nonhalting one at a time, twelve of them in Maja Kądziołka's busycoq library and Skelet #17 last, in Coq-BB5 itself. Georgi Georgiev (Skelet) had already listed all of them as holdouts of his bbfind program in 2003. Skelet #1 is a translated cycler, but it only starts repeating after about 5.4·1051 steps, with a period of more than 8 billion. The diagrams show 20,000 steps; counters are drawn on a narrower tape, as in the paper.
The enumeration also produces machines whose first transitions write 0. From a blank tape, writing 0 changes nothing, so such a machine behaves like the one that starts at the first state that writes a 1. Coq-BB5's TM_to_NF renames it to start with 1RB, and if the result already has a proof, it is reused. 24 machines are settled this way: 23 reduce to FAR and WFAR certificates and one to Finned #3.
From 2022 the challenge worked on a seed database of 88,664,064 machines that survived 47 million steps. It applied six deciders in turn: cyclers (11.2 million machines), translated cyclers (73.9 million), backward reasoning (1.25 million), halting segment, finite automata reduction, and bouncers. Each has an independent reproduction in bbchallenge-deciders and a correctness proof in the bbchallenge-proofs paper. The final Coq proof replaced them with the five deciders above, but three of them work in ways none of those do.
Start from a halting configuration and ask what could have led to it, one step at a time, keeping only the cells that are forced. If every branch runs into a cell that would need two different values, the halt is unreachable. In the paper's example, 1RB0LD_1LC0RE_---1LD_1LA1LD_1RA0RA, the only way into C is B reading 0, and the only way into B is A reading 0. That step writes a 1 where the chain needs a 0, so after two backward steps there is nothing left: the machine never halts, although its forward behaviour looks chaotic.
Watch only a segment of n cells; when the head leaves it, consider every way it could come back. The graph of segment configurations is built from the n + 2 starts (blank segment, head anywhere in it or on either side). The bbchallenge-proofs paper shows that a halting machine must reach a halting node at every one of the n + 2 head positions. If some position is missing, it cannot halt. Example: the three-state 1RB1RC_0LA0RA_0LB--- with n = 2, as in the paper's figure.
A bouncer sweeps between the ends of a tape made of fixed walls and growing repeaters. Tony Guilfoyle's decider (reproduced in Rust in bbchallenge-deciders) guesses a formula from the run, then proves that one sweep maps it to itself with each repeater one copy longer. This decided 29,799 machines of the seed database; RepWL covers them in the Coq proof. Below, the formula found for machine #88,427,177, the paper's running example: 0∞ 111 (111)ⁿ 01111 (11)ᵐ C> 0∞. The table lists the steps at which the run matches it. The counts grow by one each sweep. This only shows the certificate at work; the proof is the symbolic sweep.
| Step | Repeat counts |
|---|
Paste a machine and run all eight deciders with moderate parameters. Remember that these are partial deciders: "unknown" means only that this decider, with these parameters, found no proof.
| Decider | Parameters | Result |
|---|
The machines studied here are six-state holdouts, so by definition every decider above, run with any parameters anyone has tried, has failed on them. The techniques still carry over as tools.
tools/py/bbtools/ctl.py searches for a closed tape language from windows of K cells, and tools/lean/TM/CTL.lean checks it in Lean with a soundness theorem (not_halts). This is the CTL argument of n-gram CPS and FAR, with the same split as Coq-BB5's FAR and WFAR: an expensive search that produces a certificate and a cheap checker that the proof trusts.1RB0LF_1RC0LB show that no DFA of up to seven states closes its tape. That is the situation weighted FAR was built for: an invariant that needs a counter, which a regular language cannot express.tools/py/bbtools/macro.py, the block macro simulator with run-length coding, uses RepWL's representation: words of fixed length with repeat counts. Abstracting large counts to "at least T" and branching on them, as RepWL does, would turn it into a closure check.CoqBB5/BB5/Deciders/, hardcoded machines and certificates in CoqBB5/BB5/BB5_Deciders_Hardcoded_Parameters/ (embedded here from commit ).The deciders on this page are JavaScript transcriptions written for this page (pages/src/deciders/engine.js in this repository). They are tested against the sources: every hardcoded n-gram CPS and RepWL machine is decided with its parameters, all 40 FAR and WFAR certificates verify, and the paper's examples give the paper's results. They are explanations, not part of any proof.