Busy Beaver Explorer / holdouts / 1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB

What is known about 1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB

1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB

Decided: it 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, one of the holdouts of the BB(6) search, halts when started on a blank tape, after about 1.27·10758 steps. The exact step is known, and the halt is a Lean theorem: the rules of the machine's ladder of counters are proved for every size and every number of counters with Lean's kernel, and the long run itself is evaluated inside Lean by a function that is proved correct (compiled evaluation, native_decide).

Status as of 16 November 2026.

In short

The machine halts (Lean theorem halts; two steps of it by compiled evaluation). At the visits of the right end the tape is a short front, a ladder of levels (a rung of n blocks 0111111111 and one of eight separator words) and a tail at the left end. Every level is a digit with 16 positions: a hit from the right moves it to the next position, at ten positions the hit is absorbed, at six it is passed on to the left. What lies left of a level therefore lives exactly as it would right behind the front, only 8/3 times slower. After the reset of step 27,167,343, which turned the old ladder into fuel, the tail eats two fuel blocks and leaves three new levels in every 12 hits. With 887 levels the fuel is used up, the next hit runs into the blank left end, and state C reads a 0: the halt, at a step with 759 digits.

Other proofs and outside reports

Also proved in Coq

A second proof assistant checks the same result: halt : halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB/coq. Coq 8.18 compiles it and Print Assumptions reports no axioms; the build log is next to the files. It needs no direct run first: the verified accelerated run starts on the blank tape and takes about 30 seconds; the whole file compiles in about 2 minutes. The same files are on a branch of our fork of busycoq, ready to be proposed upstream: project-thread-3u4y3s.

Community label

In the community's BB(6) tracker the machine's class is Shift-overflow structural counter. These are labels read off the run by others, not results.

What each result rests on

kernel checked by Lean's kernel alone native evaluated by compiled code trusted C or Python in the repository, exhaustive heuristic sampling, extrapolation, patterns open not known

kernel Proved in Lean, kernel-checked

The machine halts (Coq, on busycoq's definitions)

halt : halts tm c0, with busycoq's TM, halts and c0. The 16 level hits, the 9 halting hits and the two fronts are proved for every block count by busycoq's symbolic execution; stack_run (any number of hits on any ladder) and loop_ok (a shortcut run that keeps the levels as numbers and simulates only the tail cells, sound by construction) are ordinary proofs. The run from the blank tape, loop 10000 true s0 = true, is one evaluation checked by Coq's kernel (about 30 seconds; it makes no plain run of 27 million steps first and batches up to 64 tail hits per pass over the levels). Print Assumptions halt: closed under the global context. Coq 8.18.0, about 2 minutes for the file; too little fuel makes the check fail.

coq/M_1RB1LE_0LC1RE_HHH1LD_0RD1LA_0RF1RF_1RA0LB.v, coq/build.sh, coq/build.log

Levels are transparent: any list of levels, any number of hits

A call on a tape T is a run that enters T in one state and leaves it in another, whatever lies to the right; a V-hit is one call, an H-hit five. hit0 … hit15 (from the stretch theorems): a hit on a level with j + 1 blocks at each of the 16 positions is such a hit, takes 112(j+1) + c or 56(j+1) + c steps inside the level, leaves the level at the next position, and at the six passing positions makes exactly one hit on the rest. level_run: y hits in a row on one level, with closed forms for position, block count, hits passed on and steps (16 hits are one turn: 4 blocks more, 6 hits passed on). stack_run: by induction on the list of levels, y hits on a whole ladder act level by level as the table says and pass the remaining hits to the tape below. front_run: the front and its two visits per hit. haltUp_sound, frontHalt_sound: a hit below the levels that halts (in its first call, or in the fourth call of an H-hit) is a halt of the machine, with the steps made in every level before it.

lean/Odo.lean, lean/Hits.lean (from py/hits_lean.py), lean/Ladder.lean

The accelerated run is sound

crun_sound, hrun_sound: a simulator for one call on a finite tape (blank beyond), correct for every tape to the right of the call. opAdv_sound (a jump of y hits of which none or one reaches the simulated cells), opPeel_sound, opUnpeel_sound (cells read as a level, and back), opFinal_sound (the hit that halts) and loop_sound: if the run is at the configuration of a state after its step count, and loop returns N from that state, then the machine reaches a halting configuration after exactly N steps from blank tape. Which levels to read and how far to jump is chosen by code that needs no proof: a wrong choice can only make loop fail.

lean/Ladder.lean

The level rules, for every block count

A level 4n s is the cells s (0111111111)n. For each of its 16 positions and each stretch of a hit between two crossings of the level's borders, the machine's run is proved for every n ≥ 1 and every tape left and right of the level (63 theorems). A 64th and 65th theorem, last_visit_run and last_visit_halts, run the last visit on the word with all 887 levels removed (2 1 0 3 1 0 3 1 0 5, blank to the left): it halts after 278 steps. The generator checks that the stretches chain as the table says: the states in which the head leaves and comes back, that an absorbing level never touches the tape to its left, and the level after the hit.

lean/Levels.lean (from py/levels_lean.py)

The halting configurations

The machine stops exactly when it reads the symbol of a halting transition (C0); 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

Whole visits for three families of words

Reading pairs from the head leftwards (X = 0 1, Y = 1 1): V(X U) = Y Y U; V(Y3j+1 X U) = X X (Y X X)j Y U; V(Y3j+3 X U) = X X (Y X X)j Y3 U; V(Y3j+2 X X U) ends in X Y4 U. For every j and every tape to the left, 28j + const steps.

lean/Rules.lean (from py/rules.py)

A tape that halts at the left edge

On the tape 0∞ 0 1 1 1 1 1 A> the visit runs into the blank left end and halts after 17 steps. Not a tape of the run from blank.

edge_halts, lean/Rules.lean

native Proved in Lean with native_decide

The machine halts, at a step with 759 digits (Lean theorem)

The accelerated run from blank tape ends in the halting transition C0, two cells left of the leftmost 1, at step 127357002621565065257620436683386936787539470067051886613218118511080673366941072419030003169655065867449076569424641011574489482373465883365675526698891984731533897533200967458271672457393649647114596314125471135660566111943361843730621394792642277333936847623104308961000089724168905591219305595735931713864752589517911334410100233581671754237003517860991278921217226890440796227582950616514639336930819296066429511864899248696946158576194825836402868940605014639617724789550009265777033152525606033456073540691727721901256364141236872161550422869463852043401520343212555953181130714885650835768030318277837531565019874900364467386746214009188503718874282272725926187590284697947001726343238522323981475257408390954658553165337971013334254732281910474403686 (bbchallenge count). The last trip of the head to the left starts at right-end visit number 6457109013376761952964397678097307615669340968993585759245814706743742046125940261247241066403890938492170138345021775414788657246855473619762555399924006808185668177937261822888303321241424388506815212830693515134376015491900870498530843289643797903974663993452480048769041949957161985409468353341199468784692405027220745645833011312600661412072060494393516371733163287212276888; the tape then has 887 levels and is about 1.29·10379 cells long. In Lean: halts : HaltsFromBlank and halts_in : ∃ c, steps haltN init = some c ∧ step c = none, where haltN + 1 is the step above (the bbchallenge count includes the halting transition). The proof has three parts. (1) reach0: 27,172,911 steps from blank tape lead to the tape of visit 3,040, after the last reset (native_decide on the library's list simulator). (2) loop_sound (kernel): a function loop that keeps the levels as pairs of numbers and simulates only the cells left of them returns, from a configuration of the run, the number of steps to a halting configuration. (3) run0: loop returns haltN from that tape (native_decide; 3,539 simulated hits, 587 times the deepest level is written out as cells again, exact arithmetic on numbers of up to 759 digits). The axioms of halts are Lean's three standard ones and the two native_decide evaluations.

lean/Halt.lean, lean/Ladder.lean; python3 py/accel.py, halt.txt

No halt in the first 107 steps

The same run, evaluated by compiled code.

blank_runs_native, lean/Blank.lean

trusted Computed, not proved

Independent re-computation of the halt

A second implementation of the level odometer, written separately (its own cell simulator, its own measured step constants, the deepest level always simulated cell by cell), gives the same 887 levels, the same tail, the same last visit and the same 759-digit halting step. Direct simulation agrees with the accelerated run at 12,169 checkpoints in 440 windows spread over the whole run (visit number, step count and whole tape), and about 80 truncated endgames run directly to the halt stop at exactly the predicted step (the longest after 4,568,217,938,175 steps). Not observed directly: anything between step 1.2×1012 and the halt with more than about 14 levels on the tape; that part is covered by the Lean theorem above.

verify/README.md (mymodel.py, myrun.py, final.py, sim2.c)

The level table and all step constants against the machine

For 16 positions, 28 block counts (1..24, 40, 77, 200, 1000) and 13 different tapes to the left: the double visit of front + level + rest gives the level of the table and the rest that the front alone would have made of it, the head crosses the borders in the listed states, and the steps inside the level are 112 n + c (H-hit) or 56 n + c (V-hit). 5,656 cases.

python3 py/accel.py levels

Visit numbers and step counts equal the direct run's

At all 291 compared visits up to step 1.18·1011 the accelerated run has the visit number and the step count of a direct cell-by-cell run, in three variants (0, 1 or 2 levels kept in the simulated word; started at visit 3,040 or 600). The run started at visit 600 meets the reset of visit 3,006 at the right visit.

python3 py/accel.py check, c/visits.c

The same halt with every level simulated at first

Keeping the 1, 2 or 3 deepest levels in the simulated word (each level is then run cell by cell for its first hits, and no level ever has to be put back) gives the same 887 levels, the same tail, the same visit number and the same halting step.

python3 py/accel.py --defer 1 (2, 3)

The last visit, directly

Eight tapes with the 887 levels at their final positions, small block counts and the final tail 0 3 1 0 3 1 0 5: the direct run halts in C at the left edge after exactly the number of steps the formula for the last visit gives.

python3 py/accel.py last

Where a halt can come from

Closed tape languages from windows of 4, 6 and 8 cells cover the run; each allows the halting transition C0 only at the left end (blank to the left) with the right side starting 0001, 000110, 00011001 respectively. Two abstract configurations in all.

python3 -m bbtools.ctl 1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB 8 # from tools/py

The visit map as a recursion on words

V(X U) = Y Y U, V(Y X U) = X X Y U, V(Y Y X X U) = X Y4 U, V(Y Y Y S) = X X Y V(S), V(Y Y X Y Y S) = X Y4 V(S): equal to the machine on 19,312 random words and on the 724 visits they cover among the first 1,012 of the run. The words starting Y Y X Y X follow further rules not yet written down.

py/vmodel.py

No halt in the first 1012 steps

A direct simulator on blocks of 16 cells (a full lookup table, 3·109 steps a second) runs 1012 steps without a halt; the head comes to the left end only at steps 1,779 and 27,158,883.

c/mrun.c

No halt in the first 6.00×1019 steps (exact macro run)

A macro simulator (blocks of 10 cells, long runs of equal blocks crossed in one go; exact: every macro step is a run of the machine, counted step for step) ran from blank tape to step 60,000,783,412,981,265,560 without a halt. At this block size it gives the same state, head position and tape as the direct simulator after 2,000,002,519 steps. This is a bounded run and says nothing about later steps.

python3 holdouts/1RB0LB_1RC0LA_1LB0RD_1RE1RD_1RB1RF_1LA---/py/deep.py run 240, verify; holdouts/1RB0LB_1RC0LA_1LB0RD_1RE1RD_1RB1RF_1LA---/data/deep.json

heuristic Evidence only

Nothing yet.

open Open

Nothing yet.

Check it yourself

. /etc/profile.d/lean.sh      # after scripts/setup-lean.sh
holdouts/1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB/lean/check.sh      # about 4 minutes; Halt.lean is the theorem
cd holdouts/1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB/py
python3 accel.py                    # the run to the halt (20 s); --defer 1, 2, 3: the same result
python3 accel.py levels             # the level table and step constants against the machine
python3 accel.py last               # the last visit on small tapes, direct run against formula
gcc -O2 -o /tmp/visits ../c/visits.c && /tmp/visits 1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB 1e10 A 2 100000000 2 > /tmp/v.txt
python3 accel.py check /tmp/v.txt   # visit numbers and step counts against the direct run
python3 levels_lean.py > ../lean/Levels.lean ; python3 hits_lean.py > ../lean/Hits.lean ; python3 halt_lean.py > ../lean/Halt.lean ; python3 rules.py > ../lean/Rules.lean
python3 words.py ; python3 vmodel.py 3000000
sh holdouts/1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB/coq/build.sh /path/to/busycoq      # Coq proof; a checkout of the BB6 branch of ccz181078/busycoq; about 2 minutes