Busy Beaver Explorer / holdouts / 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA
What is known about 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA
1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA
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 is one of the holdouts left open by the bbchallenge project. It does not halt when started on a blank tape; the proof is in Lean, with its long computations evaluated by compiled code. This page lists what has been established about it, sorted by what each result rests on.
Status as of 13 November 2026.
In short
It does not halt (Lean theorem nonhalt, level native). The run is a sequence of rounds. At the end of a round the tape is 01001000 (01)^B T with a big block of B pairs and a short tail T. There are 1,144 classes of such tapes (one of 62 tails, B = r0 + m·x with m = 27, 45, 48 or 66 and r0 ≥ 20,000) such that every tape of a class ends its next round in a class again; the real run enters the set at B = 28,531.
In Lean, a symbolic executor whose every move is proved to be a run of the machine (kernel) runs one round for each class with x free, and the arrival from blank tape; a second proved test shows that every round end announced lies in a class. The 1,144 rounds (133 million executor moves), the arrival and the six cycle rules are evaluated by native_decide, so the result rests on the Lean kernel and the Lean compiler. Step counts are computed by the simulators (trusted), not part of the Lean statement. Tapes of the same shape with a slightly different tail do halt, so the set cannot be widened to all tails.
Other proofs and outside reports
Also proved in Coq
A second proof assistant checks the same result: H11019.nonhalt : ~ halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/coq. 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-1RB0RD_1RC0LF_1LA0LB_HHH1RE_1LB1RA_0LC0RA.
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
Sweeps over the long blocks
Eight shift rules, for every number n of words and every surrounding tape. The five sweeps of one visit of the left end, three pairs at a time: 1 C>(010101)^n → (011001)^n 1 C> (14n steps); (011001)^n A>110 → A>110 (010101)^n (22n); 1 B>(010101)^n → (010110)^n 1 B> (14n); (010110)^n B>000 → B>000 (010101)^n (22n); (011001)^n F>0 → F>0 (010101)^n (22n). And three earlier ones (f_left, b_right, e_right).
lean/Rules.lean (generated by py/rules.py)
The machine does not halt: a second proof, in Coq (busycoq)
The same argument, ported to Coq on top of busycoq's definitions: nonhalt : ~ halts tm c0. The symbolic executor is proved sound against busycoq's step, and all runs are evaluated inside Coq's kernel by vm_compute; Print Assumptions nonhalt reports no axioms. Clean build with Coq 8.18.0: about 2.5 min.
coq/H11019.v, coq/SymExecN.v; build: sh coq/build_H11019.sh /path/to/busycoq
A closed set of round ends implies that it never halts
If the run from blank tape reaches a round end A> 01001000 (01)^B T that belongs to a set S, and every round end in S reaches a round end in S after at least one step, then the machine does not halt. Its two hypotheses are proved by the replay below.
nonhalting_of_closed_set, lean/Closed.lean
A symbolic executor and the two class tests, proved sound
The executor of 1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA, adapted: tapes of cells and blocks (w)^n with n = c + a·x; shift rules with a carried word, one to three copies at a time; one machine step; at each arrival of state A at the left end a re-bracketing and a cycle rule applied N times, where N may itself be a count N0 + q·x (the subtraction is checked coefficient by coefficient). Any step that would depend on x fails. Theorems: whatever the executor does, the machine does, for every x (run_sound); a class whose run ends at the announced round end does so for every x, in at least one step (clsRun_sound); the coverage test, a finite check over one period of the remainders, implies that every announced B lies in a listed class (covers_sound); a list that passes both is closed (closed_of_checks). The 15 shift rules are proved by evaluation in the kernel.
lean/Exec.lean, lean/Classes.lean; shRTbl_ok, shLTbl_ok in lean/ExecData.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 machine does not halt
From blank tape the machine never reaches a halting configuration: nonhalt : ¬ HaltsFromBlank, from nonhalting_of_closed_set with the set of the 1,144 classes and the three claims below. Axioms used: propext, Classical.choice, Quot.sound and 16 compiled evaluations (native_decide): the arrival, the start node's class, eight chunks of classes, six cycle rules.
nonhalt, lean/Replay.lean
Six cycle rules of the tail, for all values of their counts
Each rule says: this tape 110 (01)^a 000 (01)^b T with a = a0 + 3x, b = b0 + 3y comes back, 18 to 44 visits of the left end later, with a smaller by 27 to 66 and b larger by 57 to 141, for all x and y. Each is one run of the executor without cycle rules (9,143 to 25,749 moves), evaluated by native_decide.
rule0_ok … rule5_ok, lean/ExecData.lean
Blank tape reaches the round end with B = 28,531
527,489 moves of the executor from blank tape end at 01001000 (01)^28531 T with the tail of the certificate, and that round end is in a class of the list (arrive_ok, start_ok, native_decide).
reach_set, lean/Replay.lean; lean/Arrive.lean
The 1,144 classes are closed under one round
For each class (tail T, B = r0 + m·x) the executor runs one round with x free (60,000 to 231,000 moves, 132,636,430 in all) and ends at the round end with tail T' and B' = k + c·x of the certificate; every such B' lies in a listed class. So every round end of the set reaches a round end of the set in at least one step. Eight native_decide evaluations of 143 classes each, 35 to 56 s each.
closed_set, classes_ok, lean/Replay.lean; chunk0_ok … chunk7_ok, lean/Chunk0.lean …; data lean/ClassData.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 38,989 cells have been visited and 19,487 of them hold a 1.
holdouts/triage.json
The tail cycles
Within a round the tape is 010 (01)^a 000 (01)^b T. After a start-up the tail T repeats with a fixed period: 15 visits of the left end (a − 45, b + 99; three different tails), 16 visits (a − 48, b + 99), 22 visits (a − 66, b + 141) or 9 visits (a − 27, b + 57). Each cycle is established by one symbolic run with a and b free (steps affine in both) and re-checked on numbers.
py/closure/accel.py (verify, selftest)
The closed set: how it was found, step counts
A class is a tail T (62 of them) and a remainder of B (modulo 66: 682 classes; 45: 300; 48: 144; 27: 18), with B ≥ 20,000. For each class one symbolic round with B = r + m·x, x free, ends at 01001000 (01)^B' T' with B' = k + c·x (c = 141, 99 or 57, k ≥ 41,224); every remainder B' can have lies in a class again. The simulator refuses any step whose outcome depends on x. closure.py check re-runs all classes and tests the coverage independently of the search (5 minutes). That the set is closed is now a Lean theorem (above); this tool found it and supplies the step polynomials.
py/closure/closure.py, py/closure/cert.json
The real run enters the closed set: step count, later rounds
That blank tape reaches the round end with B = 28,531 is a Lean theorem (above). Computed: from blank tape the run is at the round end with B = 28,531 after 2,340,515,329 steps (the plain C simulator gives the same step), in the class B = 19 mod 66 of its tail. The next 1,302 rounds (B up to 437 digits), computed with numbers, agree with their classes: next tail, next B and the number of steps, all exact; 684 of the classes and all 62 tails occur.
py/closure/validate.py real, c/ev.c
Checks of the simulator
Five classes at x = 0 and x = 1 against a bit-level simulator (4.1 to 4.3 · 109 steps each): state, head position, tape and step count exact. 12 defects injected into the certificate and 8 into the simulator (wrong rule increments, rules without lower bound, wrong number of rule applications, three changed transitions, a class claimed for too coarse a remainder): all 20 reported.
py/closure/validate.py plain | mutate, c/round.c
Nearby tapes that halt
The same shape with another tail can halt: of the tails that differ from one of the 62 by one pair 10 in one block (a sample, 1,141 classes), 5 classes halt for every B, for example tail 000010101010101010101010000101010100001010101010101010101010101110000101 with B = 20,002 + 3x halts after 815,565 + 122x steps (confirmed bit by bit at three values). The other 1,136 fall into the closed set after one round. Other remainders of B for the 62 tails (a sample, 1,722 classes) all fall into the closed set; none halts.
py/closure/validate.py tails | neighbours
Independent check of the closed set
A second accelerated simulator written from scratch, without the first tool's engine (verify/accel.cpp, validated against plain simulation up to 4.4·109 steps), confirms the arrival from blank tape at step 2,340,515,329 and, for every one of the 1,144 classes, four members (the two smallest, one B near 106, one near 1011) plus 7,000 random members: no halt, the next round end is exactly the predicted tail, B and step count, and lies in a listed class. 0 mismatches; the five neighbouring tails said to halt do halt. It samples B; that every B of a class behaves so is the Lean theorem closed_set.
verify/README.md, verify/run_all.sh
Related holdouts
The same table as 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC 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.498). 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.478).
tools/py/bbtools/triage.py
open Open
Nothing yet.
Check it yourself
. /etc/profile.d/lean.sh # after scripts/setup-lean.sh
holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/lean/check.sh # all Lean files, 6 to 7 min (the eight chunks of classes take 35 to 56 s each)
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/replay/gen.py --check # the model of the Lean executor: tables, arrival, all 1,144 classes with x free (6 min); without --check it rewrites the generated Lean files
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA 1000000000
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/rules.py > holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/lean/Rules.lean # regenerate the sweep rules
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/closure.py check holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/cert.json # re-run the 1,144 classes, 5 min
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/closure.py bfs /tmp/cert.json # the search itself, 5 min
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py real 120 # the real run against the classes
gcc -O2 -o round holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/c/round.c && python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py plain ./round 5 # bit-level, 3 min
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py mutate cert; python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py mutate engine; python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py mutate engine2
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py tails 420 7; python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py neighbours 500 12
gcc -O2 -o ev holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/c/ev.c && ./ev 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA 2000000000 L A 1 100000 12 | awk 'NR%300==0'
bash holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/verify/run_all.sh # independent simulator: arrival, all 1,144 classes sampled (about 2 min)