Busy Beaver Explorer / holdouts / 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC--- / explained
A 6-state Busy Beaver machine · Status as of 19 November 2026.1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---
Decided by an outside Rocq proof: it haltsA Rocq proof in busycoq pull request 100 (open, not yet reviewed by the maintainer) was compiled here, on busycoq's own definitions, with no axioms beyond Coq's own. It is their proof, not one written in this repository; the ledger below says what this repository checked on its own.
It halts. For a long time it builds a run of the word 110 at the left end and turns it into groups of sizes 4, 7, 10, 13, … that later sweeps use up: a counter with several levels. A Coq proof made here from DeepMind's engine for a neighbouring table runs that counter to its halt, on a tape of about 24360 cells.
halt : halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---/coq. Coq 8.18.0 compiles it and Print Assumptions reports no axioms; the build log is next to the files. The proof of 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD--- (DeepMind's busycoq pull request 93 engine changed for T4) with the table, the state map and the start (C) changed; the proved engine's run from blank tape, 427,055 engine steps, is one evaluation of about 4 hours. The generator is tools/coq/t4engine/proof/mkC.py.verify/M_1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LCHHH.v). The pull request is open: not merged and not reviewed by the maintainer. We compiled the file on busycoq's BB6 branch (commit 33209bc) with Coq 8.20.1 on 19 November 2026, in 15528 s: the theorem halt : halts tm c0 is stated on busycoq's own definitions of a machine and of halting, Print Assumptions reports no axioms, and the file's transition table is this machine. It is their proof, not one written in this repository. The verdict on this page rests on this proof.Each entry says what to write, which way to move and which state to enter. The machine starts in A on a blank tape (all 0s).
The machine stops when it is in F reading 1. F is entered only from E1 (writes 0, moves R): E>1 1. So a halt is the moment this pattern appears, with the head on the cell after >.
| state | reads 0 | reads 1 |
|---|---|---|
| A | 1 R B | 1 R D |
| B | 1 L C | 0 R E |
| C | 1 L D | 1 L C |
| D | 1 R A | 0 L B |
| E | 0 R D | 0 R F |
| F | 0 L C | halt |
read:write move. Red marks a halting transition. Hover a state or a row to single out its arrows.This is the real machine, simulated in your browser. Step it, play it, or jump to a step count. Below the cells is the whole visited tape in the notation of the notes: 1^5 is five 1s, and C>0 is the head in state C on a 0.
(10)7 is the word 10 seven times in a row, and the orange tag is the head. The grouping is found afresh at every step by looking for the longest repeat of a word of up to 8 cells, so it shows the counts a machine keeps on its tape without anyone having to decode them first; it is a display, not a result.The diagram stacks the tape at many moments. Sampling at each new cell shows the shape of the run as the visited region grows; sampling evenly in time shows where the head spends its time. The records list every step at which the head reaches a cell no earlier step reached, with the side, the width so far and the whole tape: the first place to look for a repeating macro structure. Click a row of the diagram to send the simulator above to that step.
The proof is this repository's own, generated from the proof for the B start. It is DeepMind's proof of busycoq pull request 93 (by Alex Havrilla) changed for this table. Coq 8.18.0 compiles it here in about 4 hours, with no axioms (Print Assumptions halt prints “Closed under the global context”). Like DeepMind's proof, it does not find a formula for the run. It builds a fast simulator, the engine, proves in Coq that every step of the engine is a true statement about the machine, and then lets the engine run the machine from the blank tape until it halts. valu42 found the same halt (427,055 engine steps from state C) and submitted it as busycoq pull request 100, built on the proof for the B start.
A copy of the table. The proof first reflects the tape, so that left and right swap, and renames the states: this machine's A, B, C, D become C, D, A, B. That gives the table 1RB1RA_1LC0RD_1LD1LB_1RA0LE_0LB0LF_0RA--- started in state C. Coq checks transition by transition that the two runs are the same up to this change, so a halt of one is a halt of the other. From here on, directions and state names are those of that table. Call this table T4. Started in B it is 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD---, proved halting the same way; started in D it is 1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---, which is still open.
One transition changed. T4 differs from T3, the table DeepMind's proof was written for (busycoq pull request 93, for 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0RD---), only in F0: 0RA instead of 0LB. Only four of the engine's rules pass through F0. In T3 they end in CfgJ, with a +1 still to be delivered to the digit on the left. In T4 they end in CfgL with 11 more on the right, and since 11 followed by D n is D (n+1), the +1 lands on the digit to the right instead. This repository restated and reproved those four rules and every lemma and engine case built on them (124 changed lines, the same as for the B start; for this machine only the table, the renaming and the start differ); the rest of DeepMind's proof is unchanged.
Digits and three moments. Write wn for the word w written n times. The proof's main word is the digit D n = 1 (11)n 00: a run of 2n+1 ones followed by two blanks. Call n its level. Runs of 1, 7, 13, 19, … ones are the digits D 0, D 3, D 6, D 9. Most of the tape is a long sequence of digits, mostly in rows of equal ones, the highest levels towards the left and the lowest at the right end. Near the left end, where the head turns, lie a few other kinds of word, among them blocks (10)b and (111)k. The proof watches the head at three kinds of moment: CfgR, state A at the word 0100, heading right over the digits; CfgL, state B heading left with a 1 just behind it; and CfgJ, state C heading left with 100 just behind it and a +1 to deliver.
Macro rules. About twenty rules say how the machine gets from one such moment to the next, for every level and every surrounding tape. Heading right, the head turns each digit D n it crosses into S n = 1 (01)n+1, a word of the same length. Heading left in CfgL it turns S n back into D n; in CfgJ it turns it into D (n+1), which is how a +1 is delivered. At the blank end of the tape the head writes two new digits D 0 and turns back. On the left, each 111 of a block (111)k is used up by one turn, so the block is a timer that allows k more round trips. And a round trip that finds two digits D 0 side by side merges them: 10 D0 D0 becomes D3 10. Rows of higher digits are merged in pairs in the same way, through a longer detour over the left part.
A counter. Together these rules make the digits a counter. Its places are the levels 0, 3, 6, …, and the number of digits in a row is the value at that place. Each pass halves a row and carries it one place up, while fresh digits D 0 keep arriving at the right end. This is binary counting with rows instead of bits, so a row of n digits lasts about log2 n passes. The halving is not exact: a row with an odd count leaves a digit over, and the proof has rules for these leftovers (it calls them defects). Where the leftovers end up depends on the parities of huge counts, and no formula for them is known. That is why the community calls such a machine a chaotic Bell.
The engine. The engine is a program written in Coq. It stores the tape compactly: the left part as a list of words with repeat counts, the digits as a list of pairs (level, how many in a row), all numbers in binary. In one engine step it looks at the tape near the head, picks the rule that applies, often a whole batch of them (k round trips at once, with k found by a division), and writes down the result. Where no rule fits, it makes single machine steps. One theorem, proved for every possible compact tape, says that each engine step is correct: the machine really goes from the tape before to the tape after, and when the engine reports a halt, the machine really halts.
How it stops. In this machine's own terms it halts only when state B reads a 1 and the two cells to its right are 1 too: B1 and E1 then put F on a 1. Nothing in the proof predicts when the leftovers will set this up; the engine simply runs until they do. Coq's virtual machine (vm_compute) evaluates the engine from the blank tape with a budget of 219 = 524,288 steps, and it stops after 427,055 of them, when the tape holds about 24360 cells. So the computer checks one long but finite computation. What holds for all sizes (the rules, the batches, the correctness of every engine step) is proved by symbolic reasoning in Coq.
Each time the head reaches the left end in state B, the tape reads
B> 00 (110)^k (10)^a₁ 1 (10)^a₂ 1 (10)^a₃ 1 …
a prefix of k words 110, then a list of groups. Between resets the prefix grows by two words a visit, and the sweeps merge groups so that the list becomes long runs of equal sizes 4, 7, 10, 13, 16, …; at step 2.8·108 it starts
2 4^140 3 1 7^514 10^28 13^105 16^3 15 1 4 19^21 18 22 25^3 23 …
(4^140: 140 groups of size 4 in a row).
When the list is used up far enough, the prefix is turned into about k/2 groups of size 4 and a new round starts. Large and small resets alternate:
step k list after the reset 136,979,965 1670 2 3 4^835 7^38 6 1 10^170 9 13^5 16^35 … 143,004,220 220 2 3 4^110 7^108 5 1 5 1^2 … 336,918,693 2591 1 1 4^1295 3 1 7^70 6 10^257 13^14 16^53 … 354,166,720 397 1 1 4^198 3 1 7^197 5 1 5 1^2 … 528,837,280 3185 2 3 4^1592 6 7^98 6 1 4 10^323 9 7 13^16 …
The multiplicities of the sizes 4, 7, 10, 13, … act like the digits of a counter with several levels; the rule by which they carry is not worked out.
This machine's table, mirrored and with its states renamed, is 1RB1RA_1LC0RD_1LD1LB_1RA0LE_0LB0LF_0RA--- started in state C; 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD--- (state B), 1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB--- (state D) are the same table started in the other two states. It differs in the single transition F0 from the table of 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0RD---, which DeepMind proved halts (busycoq PR 93) with a fast engine: an evaluator over run-length tapes of macro words whose every step is proved sound in Coq. All of that engine's rules hold for this table except four, the ones that pass through F0. In those, where DeepMind's machine ends in the configuration <C 100, this one ends in <B 1 with 11 more on the right; on the digit words D n = 1 (11)^n 00 of the engine, this moves a carry from the digit on the left to the digit on the right.
We changed the engine at every place that uses one of the four rules (tools/coq/t4engine), extracted it from Coq to OCaml and checked it against direct simulation through 1.2×1010 machine steps. Run from blank tape in state C, it stops after 427,055 of its steps, on a tape of about 24360 cells, with the head in state F on a 1: a halt. The proof of the same table started in state B (holdouts/1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD---/coq), which redoes DeepMind's soundness proofs for the four changed rules, needs only its table, its state map and its start changed for this machine. Coq checks the run in one evaluation, so the halt is a theorem (holdouts/1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---/coq).
The machine stops only if the head in state F reads a 1. In 109 simulated steps it never does, and the accelerated simulator saw no halt in 1.48×1014 steps. The engine run above reaches the halt much later, on a tape of about 24360 cells, so the machine runs for more than 101312 steps; the exact count is not computed.
Left of the start, the visited part of the tape grows like the square root of the step count, the signature of a head sweeping back and forth across the whole tape and adding a cell or a few at the end of each sweep (a bouncer-like shape) (fitted exponent 0.5). Right of the start it grows like the logarithm of the step count: each new cell costs a roughly constant factor more time, the signature of a counter or of a Collatz-like map whose values are written on the tape (fitted exponent 0.1).
After 109 steps the tape spans 39,716 cells (26,775 left of the start, 467 right), with a density of 1s of 0.557.
The tape (run-length coded, 1^5 is five 1s, C>0 the head in state C on a 0) at some of the last moments the head reached a new cell, cut to 400 characters:
| side | step | tape |
|---|---|---|
| left | 955,797,201 | B>0 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 |
| left | 971,470,383 | B>0 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 |
| left | 987,135,381 | B>0 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 |
| right | 551,744,226 | 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0 |
| right | 706,332,105 | 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0 |
| right | 865,548,891 | 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0 |
These are measurements of one bounded run, sorted by tools/py/bbtools/triage.py; the macro structure behind them is the next thing to find.
The two machines run for the same number of steps and are drawn the same way, a row each time the head reaches a new cell. Where the relation involves a mirror image, the second diagram is flipped left to right so that the two can be compared directly. Look for where the pictures agree and where they part: the text under each relation in the section on related machines says which of it is proved and which is only observed.
Status as of 19 November 2026. The same list as the proof-status page, built from the same file.
step_none_iff, lean/Blank.leanThe machine stops exactly when it reads the symbol of a halting transition (F1); the generated statement covers every configuration.
blank_runs_kernel, lean/Blank.leanThe list simulator of the shared library, proved to agree with the machine's semantics, runs 10,000 steps from blank tape without a halt, evaluated by Lean's kernel.
blank_runs_native, lean/Blank.leanThe same run, evaluated by compiled code.
holdouts/triage.jsonThe C simulator tools/c/triage.c runs 109 steps without a halt; at the end 39,716 cells have been visited and 22,109 of them hold a 1.
tools/py/bbtools/triage.pyLeft of the start, the visited part of the tape grows like the square root of the step count, the signature of a head sweeping back and forth across the whole tape and adding a cell or a few at the end of each sweep (a bouncer-like shape) (fitted exponent 0.5). Right of the start it grows like the logarithm of the step count: each new cell costs a roughly constant factor more time, the signature of a counter or of a Collatz-like map whose values are written on the tape (fitted exponent 0.1).
c/sim.c, c/resets.pyAt each visit of the left end in state B the tape is B> 00 (110)^k (10)^a₁ 1 (10)^a₂ 1 …. Between resets k grows by 2 a visit and the sweeps merge the groups into runs of sizes 4, 7, 10, 13, …; at a reset the prefix becomes about k/2 groups of size 4. Large and small resets alternate (k = 909, 37, 1670, 220, 2591, 397, 3185 between steps 3.6·107 and 5.3·108). Observed in simulation, not proved.
holdouts/1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA1RF_0LC---/py/rsim.py, holdouts/1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA1RF_0LC---/py/rsim_screen.py, holdouts/1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA1RF_0LC---/data/rsim_screen.jsonObserved, not proved: the accelerated simulator rsim.py ran 1.48×1014 steps from blank tape without reaching a halting transition. Its tape, state and head position were equal to those of a plain C simulator at 6 checkpoints, the last at 1.00×1010 steps. Of these steps, the part after the last checkpoint rests on the simulator alone, including 12,476 trip-level jumps: a jump applies many identical round trips at once after seeing the same tape shape recur with constant count changes, which is validated against direct simulation but not proved.
t4_collision, t4_collide, t4_finishP, t4_defect0, lean/T4Rules.leanFor every tape on either side and every count, the four macro rules of DeepMind's engine for 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0RD--- that pass through F0 hold here in a changed form: each ends in state D with 11 more on the right instead of in state A (collision, collide, finish and defect: 10, 39, 2b+9 and 8m+39 steps).
halt, coq/H127983.v; generator tools/coq/t4engine/proof/mkC.pyThe engine of busycoq PR 93, with the four rules that pass through F0 changed and every lemma built on them redone (the proof of 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD---, retargeted to this table and start C), reaches a halting configuration from blank tape after 427,055 engine steps, on a tape of about 24360 cells. Coq 8.18.0 checks the run in one evaluation (about 4 hours); Print Assumptions halt: closed under the global context.
holdouts/related.json, written by holdouts/related.py compute (tools/c/cfgmatch.c, tools/c/lockstep.c)The same table as 1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB--- up to renaming and mirroring, started in another state; no common configuration in the first 107 steps of each. The same table as 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD--- up to renaming, started in another state; no common configuration in the first 107 steps of each.
. /etc/profile.d/lean.sh # after scripts/setup-lean.sh
holdouts/1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---/lean/check.sh
gcc -O2 -o sim holdouts/1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---/c/sim.c && ./sim 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC--- 600000000 1 | python3 holdouts/1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---/c/resets.py
sh holdouts/1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---/coq/build.sh /path/to/busycoq # the Coq proof; a checkout of busycoq's BB6 branch; 1 to 4 hours