Busy Beaver Explorer / holdouts / 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC
What is known about 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC
1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC
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 a symbolic checker that the kernel proves sound, the round trips evaluated by the kernel and the long runs by compiled code (native_decide). This page lists what has been established about it, sorted by what each result rests on.
Status as of 8 November 2026.
In short
It never halts. Lean proves nonhalting: from blank tape the machine reaches one of 62 tape templates and moves from template to template forever. The 62 round trips are checked by the kernel; the start and the 62 ends of an epoch (2.5 million symbolic moves) by native_decide.
What it does. Each time B reaches the left end the tape reads B> 00 (01)a 000 (01)b 000 …, a list of counts separated by short words. The rightward sweep turns 010101 into 011001 and the leftward sweep turns it back. Each round trip takes 3 from a, while the end of the list runs through one of four periodic patterns (periods 15, 22, 16 and 9 round trips) and b gains 99, 141, 99 or 57 per period. When a is used up, b takes its place and a new, longer epoch begins: the first counts of successive epochs are 4, 12, 20, 38, 68, 122, 240, 484, 1002, 2104, 4375, ….
Why it cannot halt. Only D reading a 0 halts, after C>1 0. Every round trip of every pattern and every way an epoch can end has been checked as a symbolic run with the counts as variables, and each lands on a template again; a potential on the counts shows that an epoch always ends with the second count large enough for those runs.
Other proofs and outside reports
Also proved in Coq
A second proof assistant checks the same result: H36670.nonhalt : ~ halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in tools/coq/busycoq/H36670. Coq 8.18 compiles it and Print Assumptions reports no axioms; the build log is next to the files. A shorter proof of the same theorem (a 668-line checker for tapes with two blocks of unknown length and a 58-line file with four seed tapes; Coq 8.20.1 checks it in about 25 seconds) is on a branch of our fork of busycoq, ready to be proposed upstream: bb6-nonhalt-1RB0LF_1LC0LA_1RA0RD_HHH1RE_1LA1RC_0LB0RC.
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 (D0); 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
Shift rules
B with a 1 behind it turns each 010101 into 011001 going right (14 steps a copy); C with 110 ahead turns each 011001 back into 010101 going left (22 steps a copy).
sweep_right, sweep_left, lean/Rules.lean
The halting situations
C>1 0 halts after one step, E>1 1 0 and F>1 1 0 after two, D>1 1 1 0 after three.
halt_C, halt_E, halt_F, halt_D, lean/Rules.lean
A verified symbolic checker
lean/SymCheck.lean: configurations whose tape is a list of cells and runs wn with n linear in some variables; auto finds the moves itself (a run crossed by a shift rule found on the spot, else one step) and compares normal forms at the left end. auto_reach proves that a successful check means the machine makes that run, for every value of the variables.
auto_reach, lean/SymCheck.lean
The 62 round trips
Each phase template B> 00 (01)3k+4 000 (01)3j+β rest at [k+1, j] reaches the next phase at [k, j + dj] (200 to 2,500 symbolic moves each), evaluated by the kernel. The tables also show that j + 2k + pot never decreases in a round and is at least 215 after an epoch.
round_0 … round_61, tables_ok, lean/Cert.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
The 62 ends of an epoch
Each template at [0, j+200] reaches a template again, with the old second count as the new first (4,200 to 127,000 symbolic moves each, 2.5 million in all), evaluated by compiled code; the kernel runs out of memory on runs this long.
ends_ok, lean/Cert.lean
The start
From blank tape the machine reaches template 31 (pattern R1, phase 16) with first count 118 and second 496, at step 1,277,431 (147,895 symbolic moves).
start_ok, lean/Cert.lean
It does not halt from blank tape
The invariant “at a template with j + 2k + pot ≥ 215” holds at the start and is restored after a round or an end, each taking at least one step, so the run is defined for every length. #print axioms lists propext, Quot.sound and the two native_decide axioms.
nonhalting, lean/Cert.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 39,660 cells have been visited and 19,822 of them hold a 1.
holdouts/triage.json
D never reads a 0 in 2·108 steps
In the first 2·108 steps the machine is in state D 22,202,037 times, every time on a 1: the halting transition D0 is never close to firing in a way the run shows.
c/visits.c
Related holdouts
The same table as 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA up to renaming, started in another state; no common configuration in the first 107 steps of each.
holdouts/related.json, written by holdouts/related.py compute (tools/c/cfgmatch.c, tools/c/lockstep.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.497). 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.507).
tools/py/bbtools/triage.py
Four regimes, growing epochs
How the templates were found: along the run, the list at the left end settles each epoch into one of four periodic patterns of period 15, 22, 16 or 9 round trips, in which the first count drops by 3 per trip and the second grows by 99, 141, 99 or 57 per period. Concrete simulations from every phase and residue return to a pattern.
py/regimes.py, py/endcases.py
open Open
Nothing yet.
Check it yourself
. /etc/profile.d/lean.sh # after scripts/setup-lean.sh
holdouts/1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC/lean/check.sh
python3 holdouts/1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC/py/cert.py # rewrites lean/Tables.lean
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC 1000000000