Busy Beaver Explorer / holdouts / 1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB
What is known about 1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB
1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB
Decided: it never haltsProved in this repository, checked by Lean and by Coq. The ledger below says what each part rests on.
This six-state, two-symbol Turing machine was one of the holdouts left open by the bbchallenge project. It does not halt from blank tape: Lean proves it with the kernel alone, from a table of phase rules proved for all sizes and a linear invariant on the phase forms. This page lists what has been established about it, sorted by what each result rests on.
Status as of 9 November 2026.
In short
It never halts. Lean proves nonhalting (kernel only; axioms propext, Classical.choice, Quot.sound). From blank tape the machine reaches a phase form whose counts satisfy an invariant Good, a set of linear inequalities, and every move of the branch table (one cycle iterate and one exit rule, 20 cases) leads, after at least one step, to a form that satisfies it again.
What it does. The run alternates between two kinds of phase. In a right phase the head never visits the left end: the tape is (1110)a (1111110)k 111 001 (10)m, and each visit to the right end moves one copy from the run of 10 to the run of 1111110, keeping k + m fixed. In a round-trip phase the tape seen from the left end is 0… (1000)a (10)b wc with the 14-cell word w = 00000010000010 (two copies of the old 7-cell word rewritten); c falls while a and b grow, and when c reaches 0 the next right phase starts. Each phase is longer than the previous one (round-trip phases from 0.8 to 2.0·106 and from 6.4 to 20.8·106 steps), which is why the tape grows like the square root of time on average but in bursts.
Where a halt would come from. Only B reading a 1 halts. B is entered from A reading a 0 and from F reading a 1, both stepping right; so A>0 1 and F>1 1 halt (halt_A, halt_F). In the run B always reads a 0.
Other proofs and outside reports
Also proved in Coq
A second proof assistant checks the same result: H113677.nonhalt : ~ halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in tools/coq/busycoq/H113677. Coq 8.18 compiles it and Print Assumptions reports no axioms; the build log is next to the files.
An outside proof is waiting for review: it never halts
busycoq pull request 44 (Alk, 2026-11-05) contains a Rocq proof that this machine never halts (verify/M_1RB0LE_1RCHHH_1RD1RE_1LA0RF_0RC0LA_0LC0RB.v). As of 19 November 2026 it was open: not merged, not reviewed by the maintainer, and not compiled here unless the ledger below says so. It agrees with the proof here.
Community label
In the community's BB(6) tracker the machine's class is Bell-like. These are labels read off the run by others, not results.
What each result rests on
kernel Proved in Lean, kernel-checked
The halting configurations
The machine stops exactly when it reads the symbol of a halting transition (B1); the generated statement covers every configuration.
step_none_iff, lean/Blank.lean
No halt in the first 10,000 steps
The 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_kernel, lean/Blank.lean
Every way to a halt
Two steps before any halt the machine is in 0 D>x 1 1, D>1 1 1 or 0 D>0; no other configuration halts within three steps.
halt_route, lean/Route.lean (written by py/route.py)
Five passes
C moving right crosses (10)n unchanged; A moving left crosses (01)n (8 steps a copy); F turns (1000)n into (1110)n and B turns 0 (0001)n into (1110)n 0 moving right; A turns (0111)n into (0010)n moving left. All for any n.
pass_10_right, pass_10_left, fill_F, fill_B, clear_A, lean/Rules.lean
The halting situations
A>0 1 and F>1 1 halt after two steps; these are the only ways into B reading a 1.
halt_A, halt_F, lean/Rules.lean
The 4-visit cycle, for all sizes
Inside an odd round-trip phase the left-end visits repeat a cycle of four tape shapes. With S1 a b c = 0∞ A> 07 (1000)a 0000 1 00000 1 000 (10)b (00100000100000)c 001 00000 1 000 101, the machine goes from S1 a (b+2) (c+2) to S1 (a+3) (b+14) c in 80a + 72b + 1356 steps, for all a, b, c; cycle_iter applies it k times. Step 824,136 from blank is S1 80 219 59; the same cycle, with (a, b, c) = (30424, 87941, 19564), is running at step 1.044·1011 (c/phases.c).
cycle, cycle_iter, lean/Cycle.lean (written by py/cycle.py)
The two cycles of an even phase
An even round-trip phase runs a 5-visit cycle on T3 a x d y z c = 07 (1000)a (10)x (0010)d (10)y 0000 1 00000 1 000 (10)z (00100000100000)c …, which goes to (a+4, x+8, d−5, y+7, z+5, c−2), and then a 3-visit cycle on T2 a x y c = 07 (1000)a 0000 1 00000 1 000 (10)x 0 (01)y (00000001000001)c 000 101, which goes to (a+3, x+7, y+5, c−2). Both are proved for all sizes, with their k-fold iterates.
cycle2, cycle3, cycle2_iter, cycle3_iter, lean/Cycle.lean
A whole odd phase and the right phase after it
With O a b c = 0∞ A> 07 (1000)a (10)b (00001000001000)c 101 and EF a q = 0∞ E> 00000 (0001)a (00000100000001)q 00000 1 07 1 00000 1 000 101: from O a (2p+7) (2j+3) the machine reaches EF (a+4+3j) (p+6j+8), for all a, p, j. The proof chains the entry into the 4-visit cycle, j turns of it, the exit into a right phase, the right-phase cycle (one copy of 10 becomes one copy of 1111110, proved for any number of turns) and the start of the next even phase. The odd phases starting at steps 29,301, 808,896 and 27,629,379 (O 14 37 11, O 79 219 61, O 467 1283 361) meet its conditions, and the even phases the simulation finds next are EF 30 47, EF 170 288 and EF 1008 1720.
odd_phase, oentry, oexit, rcyc_iter, rend, lean/Phase.lean (written by py/phase.py)
The branch table, for all sizes
Besides the cycles and odd_phase, Lean proves for all values of the parameters: the entry of an even phase, EF (a+7) (q+5) → T3 5 14 a 8 7 (q+2); the five exits of its 5-visit cycle by the number d < 5 of 0010 left (d = 0, 3, 4: two runs of 10 merge into T2; d = 1, 2: three runs, the middle one frozen, form U3); the 4-visit cycle of U3; the exits of the two- and three-run round trips into right phases RG and RG3, for both parities of the 14-cell words left; the cycles of those right phases; their ends when the run of 1111011 has even length (into O, or into T2); and the exit of the 4-visit cycle with no 14-cell word left (sexit0, into the right phase RF). lean/Ends.lean adds the other parities: RG and RG3 ending with an odd run of 1111011 start a 5-visit round trip T3 directly (gendo', g3endo'), and RF ending with an even run of 1111110 gives O a 0 c (rende'), which is an S1 after one pass (ozero, t3_s1). With these every form has a rule for each residue of its counts. Every rule is a symbolic run checked by the kernel, followed by a re-bracketing proof. Each rule states its exact step count.
eentry, texit0–texit4, ucyc_iter, t2exit0/1, uexit0/1, gcyc_iter, g3cyc_iter, gend', g3end', sexit0, lean/Branch.lean (written by py/branch.py), gendo', g3endo', rende', ozero, lean/Ends.lean (written by py/ends.py)
The table carries the run to step 5.7·1029
From blank tape the machine reaches O 14 37 11 in 29,301 steps (blank_O). From there, 196 moves, each a rule of the table or a k-fold iterate of a cycle with concrete arguments, reach T2 34158019330534 128092572489511 160237983842729 41908435347077 (table_run, table_from_blank), at step 572,161,236,689,394,206,666,641,378,531 by the rules' step counts. The first odd right-phase end, RG 3564802 8141369 4104765 1 at step 1.08·1015, is among them. py/table.py 1e300 writes the 2,280 moves to step 5.6·10299, which Lean also checks (about 90 seconds).
table_from_blank, lean/Table.lean (written by py/table.py from the replay py/macro.py)
The invariant
Good gives, for each of ten forms (O a b c with b large, O a 0 c, S1, RF, EF, T3, T2, U3, RG, RG3), 3 to 16 linear inequalities with integer coefficients: the growing counts keep their ratios in a polyhedral cone that every move maps strictly inside the next one; the bounded counts stay in range and T3, U3, RG3 keep exact relations (for example x = 2a + 4 in T3); and a positive linear size, which every move multiplies by at least 1.1, stays above a threshold. These give every offset the rules need, and c ≥ 2⌊d/5⌋ + 3 in T3, so the 5-visit cycle never runs out of words. good_step proves each of the 20 cases with one move lemma and omega; the end of table_from_blank satisfies Good (decide).
Good, good_step, mv_*, lean/Closed.lean (written by py/closed.py)
It does not halt from blank tape
From good_step and table_from_blank: the run from blank tape is defined for every length. #print axioms nonhalting lists propext, Classical.choice and Quot.sound; no native_decide.
nonhalting, lean/Closed.lean
native Proved in Lean with native_decide
No halt in the first 107 steps
The same run, evaluated by compiled code.
blank_runs_native, lean/Blank.lean
trusted Computed, not proved
No halt in the first 109 steps
The C simulator tools/c/triage.c runs 109 steps without a halt; at the end 56,767 cells have been visited and 20,806 of them hold a 1.
holdouts/triage.json
The replay agrees with the simulation up to 3·1010 steps
py/macro.py replays the run with the table's rules only and predicts 49 configurations before step 3·1010, each with its exact step. The plain C simulator (c/checkpoints.c) finds every one of them on the tape at exactly that step: state, head position and every cell. The phase boundaries of c/boundaries.c (29,301, 191,775, 808,896, 6,370,604, 27,629,379, 223,234,215, 3,043,404,308, 22,249,365,380) are among them. So within 3·1010 steps every branch the run takes is in the table.
py/macro.py --checkpoints, c/checkpoints.c
heuristic Evidence only
Growth shape: sqrt/sqrt
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.465). 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.529).
tools/py/bbtools/triage.py
A right phase
From step 1,896,095 to about 6.38·106 the head never reaches the left end. At the right-end visits the tape is (1110)170 (1111110)k 111 001 (10)m with k + m = 578 (k = 12 at step 2,148,568, 468 at step 6,188,728).
py/shape.py 6.5e6 LR
A round-trip phase
At the left-end visits from 824,136 to 1,896,095 the tape is 0… (1000)a (10)b wc plus short joints, with (a, b, c) going from (80, 219, 59) to (165, 555, 3). The next such phase starts at step 6,384,890 with c = 287.
py/shape.py 1e7 L 25
How the invariant was found
Not part of the proof. The forms' counts at the form entries along the replay, divided by their sum, give a cloud of points per form. A fixpoint of linear programs over the 20 moves (homogeneous parts, margin 10-3) enlarges their convex hulls until each move maps every cone inside the next; a second linear program finds the size function. Along the replay every form entry from the 39th on satisfies Good.
scratch scripts (scipy); the resulting inequalities are the data in py/closed.py
open Open
Nothing yet.
Check it yourself
. /etc/profile.d/lean.sh # after scripts/setup-lean.sh
holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/lean/check.sh
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB 1000000000
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/route.py # writes lean/Route.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/rules.py # writes lean/Rules.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/cycle.py # writes lean/Cycle.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/phase.py # writes lean/Phase.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/branch.py # writes lean/Branch.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/ends.py # writes lean/Ends.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/table.py # writes lean/Table.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/closed.py # writes lean/Closed.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/macro.py # the replay, to 1e300 steps
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/macro.py --checkpoints checks.txt 3e10
gcc -O2 -o checkpoints holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/c/checkpoints.c && ./checkpoints checks.txt
gcc -O2 -o boundaries holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/c/boundaries.c && ./boundaries 3e10
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/shape.py 1e7 L 25
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/shape.py 6.5e6 LR 60