Busy Beaver Explorer / holdouts / 1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE / explained
A 6-state Busy Beaver machine ยท Status as of 18 November 2026.1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE
Decided: it haltsProved in this repository, checked by Coq on busycoq's own definitions of a machine and of halting (there is no Lean proof of the whole run). The ledger below says what each part rests on.
It halts. For a long time it writes a list of blocks of 1s and merges them round after round. Underneath, it is a slowed-down copy of a table one transition away from a machine DeepMind proved halting, and that table, started where this one starts, halts: a Coq proof made here shows it.
halt : halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE/coq. Coq 8.18.0 compiles it and Print Assumptions reports no axioms; the build log is next to the files. The lemma detour reduces it to the T4 table started in A; the rest is the proof of 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD--- (DeepMind's busycoq pull request 93 engine changed for T4) started in A, whose run of 350,227 engine steps is one evaluation. The generator is tools/coq/t4engine/proof/mkA.py.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 E reading 1. E is entered only from D0 (writes 1, moves L): 1 D>0; F1 (writes 0, moves L): 1 F>1. So a halt is the moment one of these patterns appears, with the head on the cell after >.
| state | reads 0 | reads 1 |
|---|---|---|
| A | 1 R B | 1 R A |
| B | 1 L C | 0 R D |
| C | 1 L D | 1 L B |
| D | 1 L E | 0 L F |
| E | 0 R A | halt |
| F | 0 L B | 0 L E |
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, submitted to busycoq as pull request 109. 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 110 minutes (with other jobs running), 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.
A detour. Exchange the names E and F. Then every transition is that of the table 1RB1RA_1LC0RD_1LD1LB_1RA0LE_0LB0LF_0RA--- (call it T4) except D0. T4's D0 writes 1 and moves right into A. Here D0 writes 1 and moves left into E; on a 0, E writes 0 and moves back right into A, which reads the 1 just written and moves right again in A. Three steps lead to T4's next configuration. On a 1, E has no transition and the machine halts. The Coq lemma detour turns any halt of T4, from any tape, into a halt of this machine. So it is enough to show that T4 started in state A halts. No reflection is needed, and the state names below are this machine's. T4 started in states B and C is 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD--- and 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---, proved halting the same way.
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 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. The blocks 1^(6m+1) of the sections below are the digits D 3m. 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. T4 halts only when its state F reads a 1; in this machine's names that is E reading 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 350,227 of them, when the tape holds about 23562 cells. This machine halts there too, or earlier at a detour. 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 of the tape in state E, the tape is a list of blocks of 1s separated by 00. Almost every block has length 6m + 1 (1, 7, 13, 19, …), and equal blocks stand together: on the right a long run of blocks 1, then a run of blocks 17, then 113, and so on, the longest on the left. A handful of irregular blocks sit between the runs.
The last round ends of a 109-step run, with the number of blocks of each length:
| step | 1 | 7 | 13 | 19 | 25 | 31 | 37 | 43 |
|---|---|---|---|---|---|---|---|---|
| 207,427,257 | 234 | 896 | 40 | 192 | 3 | 37 | 0 | 8 |
| 266,253,684 | 2260 | 117 | 448 | 20 | 95 | 1 | 18 | 0 |
| 326,503,961 | 286 | 1130 | 58 | 224 | 10 | 47 | 1 | 9 |
| 417,668,259 | 2814 | 143 | 564 | 29 | 112 | 5 | 23 | 1 |
| 511,016,052 | 356 | 1407 | 71 | 281 | 14 | 56 | 3 | 11 |
| 653,806,000 | 3526 | 180 | 702 | 35 | 140 | 7 | 28 | 2 |
| 800,860,207 | 453 | 1764 | 89 | 350 | 18 | 69 | 4 | 14 |
Read down a diagonal of the table: the count of blocks of length 6m + 1 in one row is about half (within a few blocks) the count of blocks of length 6(m − 1) + 1 in the row before. So each round pairs up the blocks of every run and turns each pair into one block six cells longer, while a new run of blocks 1 is added on the right, alternately long and short. In this sense the tape holds numbers written in a base-2 like system, one run per digit position.
The rounds are made of sweeps the head does in one go; Lean proves 8 of them for all lengths (lean/Rules.lean). Inside a round the head goes back and forth across most of the tape, turning at a point that moves left a few cells per trip, and each trip adds a few cells on the right. That is why the right side of the tape grows like the square root of the step count, and the left side, which grows only at round ends, like its logarithm.
The only halting transition is E1. State E is entered by D0 (write 1, move left) and by F1 (write 0, move left), so the machine halts exactly when one of these moves lands on a 1. At the left end the head enters E on blank tape and goes on; inside the block list the irregular blocks at the run boundaries are where such a landing could happen. Nothing seen so far does it, and no invariant that rules it out is known.
Exchange E and F. Then every transition is the one of the table 1RB1RA_1LC0RD_1LD1LB_1RA0LE_0LB0LF_0RA--- (T4) except D0. T4's D0 writes 1 and moves right into A. Here D0 writes 1 and moves left into E; on a 0, E0 writes 0 and moves back right into A, which reads the 1 just written and, with A1 1RA, moves right in A: three steps to T4's configuration. On a 1, E halts. So this machine follows T4's run from state A, three steps for each D0, unless it halts at a detour first.
T4 is the table of three other holdouts, started in B, C and D; started in B it is proved halting, by DeepMind's fast engine of busycoq PR 93 changed for T4. Started in A, that engine reaches a halting configuration of T4 after 350,227 engine steps, on a tape of about 23562 cells. So this machine halts there, or earlier at a detour. Coq checks all of it (holdouts/1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE/coq).
Status as of 18 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 (E1); 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 35,915 cells have been visited and 18,041 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.071). 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.505).
lean/Rules.lean (generated by py/gen_rules.py)The head crosses a run of n copies of a short word (10, 110, 100, 011, ...) in one go, for all n and any tape around it; for example L (110)n 1 1 B> 0 R becomes L B> 1 1 (100)n 1 R in 5n + 2 steps.
c/blocks.cA C run of 109 steps reaches the left end in state E 28 times (counting only events at least 106 steps apart). Each time the tape is a list of blocks of 1s separated by 00; almost all blocks have length 6m + 1 and stand in runs of equal blocks, longest blocks on the left.
c/blocks.cFrom one round end to the next, the number of blocks of length 6m + 1 becomes about half (within a few blocks) the number of blocks of length 6(m − 1) + 1 before; a new run of blocks 1 appears on the right, alternately about 2,000 to 4,000 and about 200 to 450 long in the last rounds. A few irregular blocks sit at the boundaries of the runs.
Between round ends the head goes back and forth across most of the tape; the point where it turns moves left a few cells per trip while each trip adds a few cells on the right. This is why the right side grows like the square root of the step count and the left side, which only grows at round ends, like its logarithm.
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 6.64×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.02×1010 steps. Of these steps, the part after the last checkpoint rests on the simulator alone, including 13,093 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.
halt, detour, holdouts/1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE/coq/H181655.v (generated by tools/coq/t4engine/proof/mkA.py)halt : halts tm c0, with busycoq's TM, halts and c0 and tm this machine's table. detour: for every configuration and every n, if T4 (1RB1RA_1LC0RD_1LD1LB_1RA0LE_0LB0LF_0RA---) halts from it in n steps, this machine halts from it with E and F exchanged. The rest is the proof of 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD--- (DeepMind's PR 93 engine with the four rules that pass through F0 changed), started in A instead of B: 350,227 engine steps to F on a 1, one evaluation checked by Coq's kernel (run_ok). Print Assumptions halt: closed under the global context. Coq 8.18.0.
. /etc/profile.d/lean.sh # after scripts/setup-lean.sh
holdouts/1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE/lean/check.sh
gcc -O2 -I tools/c -o blocks holdouts/1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE/c/blocks.c && ./blocks 1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE 1000000000 L E 2 1000000
sh holdouts/1RB1RA_1LC0RD_1LD1LB_1LE0LF_0RA---_0LB0LE/coq/build.sh /path/to/busycoq # the Coq proof; a checkout of busycoq's BB6 branch; 45 minutes or more
sh tools/coq/t4engine/proof/build.sh /path/to/busycoq fast # regenerate H155900.v and H181655.v from PR 93's file (fast: final runs admitted)