Busy Beaver Explorer / holdouts / 1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE
What is known about 1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE
1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE
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 was one of the holdouts left open by the bbchallenge project. It halts: Lean and Coq each prove it, with a simulator that is proved correct and then evaluated from blank tape to the halting transition. The Coq proof also proves the exact number of steps. This page lists what has been established, sorted by what each result rests on.
Status as of 16 November 2026.
In short
It halts. Proved in Lean (halts, lean/Halt.lean): a run-length simulator with closed-form jumps is proved to follow the machine (kernel), and its run from blank tape reaches the halting transition (native_decide, which trusts Lean's compiler). It is also proved in Coq on busycoq's definitions (halts_172044, steps_172044, coq/). There the evaluation is done by the kernel's virtual machine, so that proof does not trust a compiler, and it counts every step. The number of steps, 853177647932005270554892218084645935472995035642746848454477793277027802995098762076895667304703808111420498351739937140047615589683 (about 8.53·10131), is proved in Coq: the machine reaches its halting configuration after exactly that number minus one steps and at no other time (kernel). Three separately written simulators agree with it. The tape is a binary odometer whose digits are counters of the word 011; each counter is a fuel tank that loses a unit every 2j visits of the right end. After 9.6·1065 visits the odometer is the whole tape, 2.9·1066 cells, every bit is 1, and the carry falls off the left end.
Other proofs and outside reports
Also proved in Coq
A second proof assistant checks the same result: M172044.halts_172044 : halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/coq. Coq 8.18.0 compiles it and Print Assumptions reports no axioms; the build log is next to the files. It also proves the exact number of steps (steps_172044: the halting configuration is reached after exactly 853177647932005270554892218084645935472995035642746848454477793277027802995098762076895667304703808111420498351739937140047615589682 steps, and only then). It is the method of the Lean proof with two block rules that cross a whole counter level in one round and a step count in every lemma; the run from blank tape is 19.0 million rounds, evaluated by vm_compute in about 8.5 minutes, so this proof does not trust a compiler. The theorem printed above is the halting one; steps_172044 in the same file states the count. A shorter proof of the same theorem (the same proof without step counts, 1,272 lines, checked by Coq 8.18 in about 2 minutes 45 seconds, and submitted upstream as busycoq pull request 76) is on a branch of our fork of busycoq, ready to be proposed upstream: project-thread-kihhxw.
Community label
In the community's BB(6) tracker the machine's class is Skelet 1-like Class 1. 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 (F0); 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 machine halts: a second proof, in Coq (busycoq)
halts_172044 : halts tm c0 on the definitions of busycoq's BB6 branch, with no axioms. The same method as the Lean proof (the visit rule and the closed-form jump, proved for every zone; a run-length simulator proved to follow the machine) plus two block rules that cross a whole counter level in one round (D leftwards over 1 0 (011)k 1, C rightwards over (100)m 1 0 1 1 0, proved for every k, m). They bring the run from 88.9 to 19.0 million rounds. The run from blank tape to F0 is evaluated by vm_compute, which the kernel checks: about 8.5 minutes with the step counts below (160 seconds without them, in an earlier version on the busycoq fork).
halts_172044, run_halts, coq/M_1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_HHH1LE.v
The exact number of steps: 8.53·10131
steps_172044 : halts_in tm c0 (N.to_nat K) /\ forall n, halts_in tm c0 n -> n = N.to_nat K, with K = 853177647932005270554892218084645935472995035642746848454477793277027802995098762076895667304703808111420498351739937140047615589683 minus one: the machine reaches its halting configuration after exactly K steps and at no other time, so it runs for K + 1 steps with the halting transition (the bbchallenge count). Being exact, this is also the best possible lower and upper bound. Every lemma of the Coq proof states its number of steps (busycoq's multistep). A visit takes 6(n0+…+ni−1) + 4i + 11 steps. V visits take a closed form, 11V + 6V(V−1) plus a sum over the levels of the odometer (Jz), proved by induction on V. The run carries its count and ends with run 225 start = RHalt K.
steps_172044, jump, Jz_succ, round_sound, coq/M_1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_HHH1LE.v
The visit rule of a zone, for every zone
When the tape ends in counters (011)nk … (011)n0 separated by 11 (bit 0) or 01 (bit 1), one visit is a binary increment of the bits: the lowest 0 bit si is set, ni loses 1, every bit cleared moves one unit to the counter on its left, n0 gains 2. Proved for every number of counters, every count and every tape left of the zone, by induction on the carry.
visit, lean/Zone.lean
V visits at once
In the coordinates N0 = n0 − s1, Nj = nj + sj − sj+1 a visit is a plain binary increment in which Nj−1 loses 1 when bit j is set and N0 gains 2. For every V after which the bits have not overflowed and every Nj is still at least 2, the machine goes from the zone to the zone V visits later, given in closed form.
jump, addV_succ, inc_physP, lean/Jump.lean
The simulator follows the machine
Each round of the run-length simulator (one transition, a run of a word crossed when one or two copies are crossed in the same state, a copy unpacked, or a jump whose hypotheses it has checked) takes the configuration it stands for to a configuration the machine reaches; if it answers true, the machine halts. The leftward half of the simulator is the mirror image of the rightward half (steps_mir).
mstep_sound, tryJump_sound, run_sound, lean/Sim.lean, lean/Run.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
The simulator of lean/Sim.lean and lean/Run.lean, started on blank tape, meets the halting transition F0 within 108 rounds (about 88.9 million: 68.6 million single transitions, 13.4 million runs crossed, 86,734 jumps). With run_sound this is halts : HaltsFromBlank. The evaluation is compiled, so it trusts Lean's compiler; about 6 minutes of CPU.
run_halts, halts, lean/Halt.lean
trusted Computed, not proved
The number of steps, by three Python simulators
853177647932005270554892218084645935472995035642746848454477793277027802995098762076895667304703808111420498351739937140047615589683 steps (the halting transition counted), 9.6·1065 visits of the right end. The same number as the Coq proof; the Lean proof does not count steps. py/accel.py (86,729 closed-form jumps, 116,906 visits on a run-length tape), py/odo.py (the jumps composed by doubling instead of the closed form) and py/leansim.py (the Lean simulator's algorithm, 86,734 other jumps) give the same number.
py/accel.py, py/odo.py, py/leansim.py
The Python simulators against a cell-by-cell run
py/rl.py agrees with the cell-level reference simulator on step count and whole tape at each of the first 3,000 visits, with the plain C simulator on step count and number of 1s at each of the first 20,000 visits; the visit rule with its step count 6(n0+…+ni−1) + 4i + 11 agrees with the cell-level simulator on 6,000 random zones; the accelerated run agrees with rl.py alone up to visit 429,738 and with the C run-length simulator c/tok.c at 57 checkpoints up to step 1015.
py/check.py, c/visits.c, c/tok.c
How it ends
At the last visit the tape is 1 n214 01 n213 01 … 01 n0 0 with n214 = 91,562 and n0 about 2.5·1065: every bit is 1, the carry crosses all 215 counters in one walk of 2.9·1066 steps and F reads a 0 at the left end. The word at the left end had been eaten over the previous overflows (11111101111, 11111101, 11101111, 11101, 1111, 1).
py/accel.py
Related holdouts
The same table as 1RB0LC_1LC0RE_1LD1LB_1LA1LD_1RF0RA_---1RE up to renaming and mirroring, 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
The irregular visits
When a counter runs low or the bits overflow, the words between counters change (11101, 11101111, 1101101101, …) and counters merge or split; no closed rule is known for these visits, they are simulated (in the Lean proof too). The first counter ran out four times (near 105, 1014, 1039 and 1066 visits); three times the left end recovered, the fourth time it did not.
README
open Open
Nothing yet.
Check it yourself
. /etc/profile.d/lean.sh # after scripts/setup-lean.sh
holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/lean/check.sh # about 10 minutes; prints the axioms of visit, jump, run_sound, halts
sh holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/coq/build.sh /path/to/busycoq # Coq 8.18, busycoq's BB6 branch; about 9 minutes; prints the axioms of halts_172044 and steps_172044
python3 holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/py/accel.py # the run to the halt with its step count, about 2.5 minutes
python3 holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/py/coqsim.py # the Coq simulator's algorithm in Python, about 1 minute
python3 holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/py/leansim.py # the Lean simulator's algorithm in Python, about 3 minutes
python3 holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/py/check.py quick # the checks of the Python simulators, 15 s (full: 5 min)