Busy Beaver Explorer / holdouts / 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---

What is known about 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---

1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---

Decided: it haltsProved in this repository, checked by Lean and by Coq. The ledger below says what each part rests on.

This six-state machine is on the bbchallenge list of holdouts. This page lists what has been established about it, sorted by what each result rests on. The headline: it halts from blank tape, proved in Lean.

Status as of 13 November 2026.

In short

It halts, proved in Lean (theorem halts_from_blank). The machine is a small rewriting system on the right half of its tape (the visit law, kernel-checked): blocks 000/100 are binary digits, blocks 1010 double the visits passing through, and a visit that meets 1011 halts. A checker for this system, proved correct in the kernel, finds that rounds 1 to 161,210 only rewrite and that round 161,211 meets 1011; that evaluation is by native_decide (compiled code), in ten segments. It halts after between 5.9 × 1024,266 and 9.2 × 1024,266 steps (computed, not proved).

Other proofs and outside reports

Also proved in Coq

A second proof assistant checks the same result: M_1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1REHHH.halts : halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in tools/coq/busycoq/VisitLaw2. Coq 8.20.1 compiles it and Print Assumptions reports no axioms; the build log is next to the files. It runs the same visit law for 161,210 rounds with the checker of busycoq pull request 59, extended to two forms of visit; that run is one evaluation of about 15 minutes. The same files are on a branch of our fork of busycoq, ready to be proposed upstream: bb6-halt-1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1REHHH.

Community label

In the community's BB(6) tracker the machine's class is Shift-overflow 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 halting configurations

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

The sweeps of the run

The shift rules the machine uses in its run (every sweep met when the symbolic simulator runs from many configurations of the run), each for every number of copies.

lean/Rules.lean (generated by py/rules.py)

Both counters' increments, for all sizes

One event (A on cell 3, phase 1) is the left increment (carry over n ones, digits 0110/0111) followed by the right increment in one pass: on a lowest 0 (18n+70 steps), over k+1 ones (6k+18n+76), across one junk unit (18n+110, 18n+116), across j units then k+1 ones (34j+6k+18n+82). 5 theorems.

lean/Events.lean (generated by py/events.py)

The visit law, in two forms

A visit (the head on a 0 with a 0 on its left and a stream s on its right, in state C or F; it returns in state A two cells further left) rewrites the stream by 0 s → 1 s, 100 s → 000 v(s), 110 s → 000 v(s), 1010 s → 1010 v(v(s)), and halts the machine on 1011 s; for every stream and every left tape. Both forms obey the same rules. The run is a sequence of rounds 0^inf A> 1 0 0 S → 0^inf A> 1 0 0 v(1 0 S), starting after 6 steps with S = 1 0^inf.

V_0, V_100, V_110, V_1010, V_1011_halts, W_*, round, round_halts, start, lean/Visit.lean (generated by py/visit2.py)

The abstract visit law and its count laws

The four rules and the halting pattern as inductive relations on streams, with no machine in them; the 1010 rule is guarded (the stream behind must not start with 11), and after two visits a stream never starts with 11. Under n visits, 000 r and 100 r are binary digits that pass every second visit on, and 1010 r passes 2n visits on; likewise for "one of the first n visits halts".

AV, AH, Law.av, Law.ah, av2_guard, law_Z, law_H, law_G, vs_L, hvs_*, VisitLaw.lean

A checker for the visit law, proved correct

scan carries a count of visits, kept as the pair e, c for 2e − c, through a finite word in one pass; hscan looks for a halting visit. Both are proved against the abstract system.

scan_sound, hscan_sound, round_sound, VisitCheck.lean

If the checker accepts, the machine halts

This machine satisfies the law, so for every k: if the checker runs k rounds from the word 1 and then finds a halting visit in the next round, the machine halts from blank tape. Axioms: propext, Classical.choice, Quot.sound.

law, halts_of_check_blank, lean/Law.lean; halts_of_check, VisitCheck.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 halts from blank tape

check 161210 [true] = true: rounds 1 to 161,210 use the four rewriting rules only, round 161,211 meets 1011. Evaluated with the checker compiled to native code, in ten segments chained by a kernel-checked lemma (about 3 hours of computing in all; the word grows to 1,001,253 cells). With the claim above: the machine halts. Besides the three standard axioms the theorem depends on eleven native_decide axioms, one per evaluation (trust in the Lean compiler). The number of steps is bounded separately (computed). Each segment was checked on 13 and 14 November 2026, and the whole check was run again from start to end on 14 November 2026 (HALT CHECKED). The repository's automatic checks cover the kernel-only part, not this evaluation.

halts_from_blank, lean/Halt.lean; check_run, VisitRun.lean, VisitSeg1.lean to VisitSeg10.lean; run with lean/check_halt.sh

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 248 cells have been visited and 100 of them hold a 1.

holdouts/triage.json

No halt in the first 1011 steps

A direct run of 1011 steps (longrun.c, the simulator of tools/c/tm.h) without a halt.

holdouts/1RB---_0LC0RB_1RA1LD_0RD1LE_1LF0LA_1LB0LE/c/longrun.c

The left side is clockwork

Between consecutive left-end extensions the busiest cell turns 3·2k times, each count twice (48, 96, 96, ..., 3·222), in the first 1.5·109 steps.

holdouts/1RB---_0LC0RB_1RA1LD_0RD1LE_1LF0LA_1LB0LE/c/ymax.c

How much of the run the increments cover

In the first 108 steps (513,702 events) 90.5% of the events are instances of these theorems (r0 256,841; r1 92,325; j10 75,989; j110 37,990; jk 1,733); the other 48,824 are carries over other junk layouts and the moments around the ends.

python3 py/events.py --coverage 100000000 (with c/evdump.c of 1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RB_0RC---)

The same round as the PR59 machines

The three machines of busycoq PR59 (1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RF_0RC--- and two relatives) obey the same law with one form of visit, and PR59 proves in Rocq that they halt in round 161,211. The proof here does not use PR59; our C simulator of the law (vis.c) also halts in that round on the PR59 machine. The twin 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA0RE_1RE--- has its own theorem: machines with related tables are not claimed to halt together.

busycoq PR59; holdouts/1RB0LB_0RC0LD_1LD1RE_0LA0RF_1RB0RD_0RB---/c/vis.c

Between 5.9 × 1024,266 and 9.2 × 1024,266 steps

Computed, not proved: the machine halts after between 5.9 × 1024,266 and 9.2 × 1024,266 steps (178.4·280605 to 274.6·280605). Every visit costs a fixed number of steps of its own: 4 or 8 steps for 0 → 1 (entered in C or F), 6 for 100, 8 for 110, 20 for 1010. A C program repeats the checker's pass for all 161,210 rounds and adds up the visits per rule (5.9519·280605 of each main kind in the completed rounds, at most 2.1164·280605 more in the halting round). Its final word agrees cell for cell with the word the Lean segments check; the sums are in floating point, and the bounds are widened by 0.1% for that.

c/steps.c in holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---/

Related holdouts

The same tapes at another pace, whatever the states, as 1 other holdout (listed on the explainer page).

holdouts/related.json, written by holdouts/related.py compute (tools/c/cfgmatch.c, tools/c/lockstep.c)

heuristic Evidence only

Growth shape: exp/exp

Left 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.08). Right of the start it 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).

tools/py/bbtools/triage.py

Two counters of the same events

Read off the run: the counters on the two sides of the engine both go up by 1 at every visit of the head to the engine, one of them with fixed junk stretches between some digits; the junk is written when a carry reaches the end of the tape.

README.md

open Open

Nothing yet.

Check it yourself

. /etc/profile.d/lean.sh      # after scripts/setup-lean.sh
holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---/lean/check.sh
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE--- 1000000000
python3 holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---/py/visit2.py 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE--- H60498 /dev/stdout 2>/dev/null | diff - holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---/lean/Visit.lean
holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---/lean/check_halt.sh   # the halting theorem: compiles the checker, then ten native_decide segments, about 3 hours