Busy Beaver Explorer / holdouts / 1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB--- / explained
A 6-state Busy Beaver machine · Status as of 19 November 2026.1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---
Decided by an outside Rocq proof: it haltsA Rocq proof in busycoq pull request 102 (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 writes runs of equal blocks of 1s and halves them round after round, stopping one cell short of a halt thousands of times. Underneath, it is a table one transition away from a machine DeepMind proved halting, and DeepMind's engine, changed for that transition, shows in Coq that it halts.
halt : halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---/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, the start (D) and the final run (run_pow 20) changed; the proved engine's run from blank tape, 688,228 engine steps, is one evaluation of about 12 hours. The generator is tools/coq/t4engine/proof/mkD.py.verify/M_1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RBHHH.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 49618 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 L): 1 E>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 | 0 L E |
| B | 1 R C | 1 R B |
| C | 1 L D | 0 R A |
| D | 1 L A | 1 L C |
| E | 0 L C | 0 L F |
| F | 0 R B | 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.
Watch the run only at the moments the head stands in state A at the left end of the tape. At every such moment the tape is a list of blocks 1k 00 (k ones, then two zeros), and almost every k has the form 6j+1: 1, 7, 13, 19, 25, ... Call j the block's level. Equal blocks come in long runs. Here is the tape at step 448,826,251, each block written as its k, x meaning repetition (so 7x570 is 570 copies of 1700):
58 1/1 13 53 47 49x3 43x4 41 37x18 31x23 25x92 1 17 19x113 7 1 11 13x458 1 5 7x570 5 1x2265 1
The highest levels are on the left, the lowest on the right; the whole tape is 25,736 cells wide. The left part grows only like the logarithm of the time (a new level now and then), the right part like its square root.
The next sample, at step 560,017,209, reads (the leftmost few blocks left out):
... 43x9 37x11 31x46 7 1 23 25x56 7 1 17 19x228 7 1 11 13x284 11 7x1133 1x1500 1
Compare: the 2265 blocks of level 0 became 1133 blocks of level 1, the 570 of level 1 became 284 of level 2, 458 → 228, 113 → 56, 92 → 46, 23 → 11, 18 → 9. Every run halved and went up a level, and a fresh run of 1500 level-0 blocks appeared on the right. That is the law at every round we checked: n blocks of level j become between ⌊n/2⌋−1 and ⌈n/2⌉+1 blocks of level j+1. So a run born with n blocks survives about log2 n rounds, which is why the number of levels, and the left part of the tape, grows only logarithmically.
How the halving is done: a round is an expanding bouncer. The head runs right into the tape and then zig-zags in a window that widens on both sides a few cells per trip. Going right, it rewrites pairs of ones 11 as 01; going left it rewrites 01 back as 11 (these shift rules are proved in Lean). Doing so it eats one block of a pair and grows the other by six ones.
This machine's table, with its states renamed, is 1RB1RA_1LC0RD_1LD1LB_1RA0LE_0LB0LF_0RA--- started in state D; 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD--- (state B), 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC--- (state C) 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 3×1010 machine steps. Run from blank tape in state D, it stops after 688,228 of its steps, on a tape of about 26326 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, its start and a longer final run for this machine. Coq checks the run in one evaluation, so the halt is a theorem (holdouts/1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---/coq).
The machine has one halting transition (F reading a 1), and following the table backwards there is only one way into it: D reads a 0 while the three cells to its left are 1. Lean checks that 1 1 1 D> 0 halts four steps later. In the first 109 steps D read a 0 about 21,000 times, and every single time the cells to its left were 1 1 0: the block to its left had exactly two ones. So whether the machine halts is whether some round ever brings D to a 0 next to a longer run of ones, for instance through one of the odd blocks (5, 11, 17, ...) left over when a run has an odd count.
No short invariant decides it (CTL up to 6 cells, n-gram CPS up to width 7 fail), and the round map has not been worked out. The engine run above settles it without that map: much later, on a tape of about 26326 cells, D does read a 0 next to three 1s, and the machine halts after more than 101904 steps. The exact count is not computed.
Left of the start, the visited part of the tape 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.069). Right of the start it 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.504).
After 109 steps the tape spans 37,754 cells (401 left of the start, 26,856 right), with a density of 1s of 0.618.
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 | 559,522,328 | D>0 1^3 0^2 1^15 0^2 1 0^2 1^51 0^2 1^55 0^2 1^49 0^2 1^49 0^2 1^47 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^3 |
| left | 705,188,298 | D>0 1^3 0^2 1^3 0^2 1^59 0^2 1^55 0^2 1 0^2 1^47 0^2 1^49 0^2 1^49 0^2 1^49 0^2 1^49 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^13 0^2 1^29 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 |
| left | 875,296,488 | D>0 1^5 0^2 1 0^2 1^59 0^2 1^53 0^2 1^55 0^2 1^55 0^2 1^49 0^2 1^49 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^35 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^7 0^2 1 0^2 1^29 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^ |
| right | 959,906,985 | 1^2 0 1 0 1^2 0 1^2 0 1^55 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 1^51 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 1^45 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 |
| right | 975,588,304 | 1^2 0 1 0 1^2 0 1^2 0 1^55 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 1^51 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 1^45 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 |
| right | 991,309,423 | 1^2 0 1 0 1^2 0 1^2 0 1^55 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 1^51 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 1^45 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 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 37,754 cells have been visited and 23,316 of them hold a 1.
tools/py/bbtools/triage.pyLeft of the start, the visited part of the tape 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.069). Right of the start it 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.504).
b_run, a_halve, c_halve, c_double, d_double, lean/Rules.leanMoving right, A (with 1 0 behind it) and C (with 1 behind it) turn each pair 11 into 01, 6 steps a pair: a run of 2n ones becomes (01)n. Moving left, C (facing a 0) and D (facing a 1) turn each 01 back into 11, 2 steps a pair. B runs over 1s. Each holds for every n and every surrounding tape.
halt_shape, halt_after_shape, lean/Rules.leanFrom 1 1 1 D> 0 the machine reaches F on a 1 in 3 steps and halts on the next. Conversely (by reading the table, not formalized) F is entered only from E on a 1, E only from A on a 1, and A has a 1 to its left only when it came from D on a 0, so every halt comes this way.
c/halt_nbhd.c (./halt_nbhd M 1000000000 D 0)In the first 109 steps D reads a 0 20,887 times with 1 1 0 to its left (one 1 short of a halt) and 147 times at the blank left end; never with three 1s.
c/samples.c, py/rounds.pySample the run when the head is in A at the left end of the tape (rounds; consecutive samples about 1.25 times further apart). At every sample the tape is a list of blocks 1k 00, almost all with k = 6j+1 and grouped in long runs of equal blocks, lowest level at the right. Between consecutive rounds a run of n blocks of level j becomes a run of ⌊n/2⌋−1 to ⌈n/2⌉+1 blocks of level j+1 (checked for every run of at least 10 blocks after the first 3·106 steps, to 1.7·109), and a new run of level-0 blocks 100 appears, alternately about 0.65 and 1.9 times the previous one. A few odd blocks (k = 5, 11, 17, ...) sit between the runs.
After the left-end sample the head runs right to a point well inside the tape and then zig-zags in a window whose left edge creeps left and right edge creeps right (by a few cells per bounce, using the halving and doubling rules above), until the window reaches the left end: the next sample. This is where the square-root growth on the right comes from.
tools/py/bbtools/ctl.py; tools/c/ngramcps.c (run for the G02 group, not stored here)bbtools.ctl with windows of K = 3, 4, 5, 6 cells finds a closed set, but every one allows a halt (72 to 145 halting abstract configurations); n-gram CPS (widths 3 to 7, with history and LRU) also fails.
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.90×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 6,642 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.
holdouts/1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---/lean/T4Rules.leanThe four changed macro rules are proved in Lean for 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---, the same table started in state C; they are statements about the table, so they hold here after the renaming of states, which is not itself checked in Lean.
halt, coq/H67137.v; generator tools/coq/t4engine/proof/mkD.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 D), reaches a halting configuration from blank tape after 688,228 engine steps, on a tape of about 26326 cells. Coq 8.18.0 checks the run in one evaluation (about 12 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 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC--- 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 and mirroring, 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/1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---/lean/check.sh
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB--- 1000000000
gcc -O2 -o samples holdouts/1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---/c/samples.c && ./samples 1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB--- 2000000000 A L 0 100000 > left.txt && python3 holdouts/1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---/py/rounds.py left.txt
sh holdouts/1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---/coq/build.sh /path/to/busycoq # the Coq proof; a checkout of busycoq's BB6 branch; about 12 hours