Busy Beaver Explorer / holdouts / 1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA

What is known about 1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA

1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA

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 two 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). From step 1,818,198,163,340,705 on, the configuration E> 0 (1011001)^59 1011 00000 1101100110110 (011)^16 001101100110 (011)^r comes back with r larger by 321,042,928 after 116,320,154 arrivals at the left end, for every odd r ≥ 65. In Lean, a symbolic executor whose every move is proved to be a run of the machine (kernel) replays the arrival from blank tape and one period with r = 65 + 2x, x free; the two replays and the twelve cycle rules they use are evaluated by native_decide, so the result rests on the Lean kernel and the Lean compiler. The exact step and visit counts are computed by the Python and C++ simulators (trusted), not part of the Lean statement.

Other proofs and outside reports

Also proved in Coq

A second proof assistant checks the same result: H65826.nonhalt : ~ halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/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 (the same symbolic executor and runs in one self-contained file of 1,616 lines; Coq 8.20.1 checks it in about 49 seconds) is on a branch of our fork of busycoq, ready to be proposed upstream: bb6-nonhalt-1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_HHH1LA.

Community label

In the community's BB(6) tracker the machine's class is Unknown. 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 (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

Sweeps over the long blocks

L A>(0011011)^n R → L (1100110)^n A> R (13n steps), L (1011001)^n D>1 R → L D>1 (0110110)^n R (23n steps), L A>(011)^n R → L (110)^n A> R (3n steps), for every n, L, R.

a_right, d_left, a_right3 in lean/Rules.lean

The two long phases, any number of cycles

Collecting: E> 0 (1011001)^p (101)^5 10 (011)^q 000 (011)^r (q even, r odd) becomes the same with p + 2n, q − 2n. Expanding: E> 0 (1011001)^p 1011 0^5 110110011010 (101)^m 1000 (011)^r (m even, r odd) becomes the same with p − 2n, m + 14n. One cycle each with its exact step count (48a + 48b + 72p + 476 and 240b + 240c + 144p + 2812), n cycles by induction.

collect2, collect_n, expand4, expand_n in lean/Phases.lean; collect_raw, expand_raw in lean/Rules.lean

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 40 s.

coq/H65826.v, coq/SymExecN.v; build: sh coq/build_H65826.sh /path/to/busycoq

A growth cycle implies non-halting

With C(r) = E> 0 (1011001)^59 1011 00000 1101100110110 (011)^16 001101100110 (011)^r: if the run from blank tape reaches some C(65 + 2x), and every C(65 + 2x) reaches C(65 + 2(x + 160,521,464)) in at least one step, the machine does not halt from blank tape. The two hypotheses are proved by the replay below.

nonhalting_of_growth_cycle, lean/Cycle.lean

A symbolic executor, proved sound

Tapes are lists of cells and blocks (w)^n with n = c + a0x0 + a1x1 + …, the x free. A move is a shift rule from a table (a block crossed at once, one or two copies at a time), or one machine step, and at each arrival of state E at the left end a re-bracketing of the tape and a cycle rule applied N times at once. Any step that would depend on a variable fails. Theorem: if the executor goes from S to S′ in k moves and its tables are valid, the machine goes from S to S′ for every value of the variables. The 31 shift rules are proved by evaluation in the kernel; the N-fold application of a cycle rule by induction.

run_sound, run_pos, rule_instN, ruleOK_of_run in lean/Exec.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. It combines the three claims below with nonhalting_of_growth_cycle. Axioms used: propext, Quot.sound and 14 compiled evaluations (native_decide): the two replays and the twelve cycle rules.

nonhalt, lean/Replay.lean

Twelve cycle rules, for all values of their counts

Each rule says: this tape with counts bi + 2xi comes back with counts bi + Di + 2xi, for all xi (eleven are collect or expand, plain or with inert zones in between, 2 or 4 visits; one is the drain, 72 visits, 201,007 executor moves). Each is one run of the executor without cycle rules, evaluated by native_decide.

rule0_ok … rule11_ok, lean/ExecData.lean

Blank tape reaches C(16,797,709)

5,037,044 moves of the executor from blank tape end at C(16,797,709) (arrive_run, native_decide, 13 s); by soundness the machine reaches that configuration.

reach_cyc, lean/Replay.lean; arrive_run, lean/Arrive.lean

C(65 + 2x) reaches C(65 + 2(x + 160,521,464)), for every x

5,581,714 moves of the executor from C(65 + 2x), x a free variable, end at C(321,042,993 + 2x) (period_run, native_decide, 14 s); by soundness the machine does so for every x, in at least one step.

grow_cyc, lean/Replay.lean; period_run, lean/Period.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 43,491 cells have been visited and 26,502 of them hold a 1.

holdouts/triage.json

The growth cycle: visit and step counts

C(r) reaches C(r + 321,042,928) after 116,320,154 arrivals at the left end and 650,373,336,347,246,654 + 4,382,930,856 (r − 65) steps. That C(r) reaches C(r + 321,042,928) is a Lean theorem (above); the counts come from two symbolic simulators that agree (py/closure/accel.py and the model of the Lean executor, py/replay/engine.py), checked against numeric runs from C(65), C(67), C(79) and three periods of the real run; 17 injected defects are all reported.

py/closure/cycle.py check, mutate, instance; py/replay/gen.py --check

Blank tape reaches the cycle: step counts

That blank tape reaches C(16,797,709) is a Lean theorem (above). The step counts are computed: the run is at C(16,797,709) after 1,818,198,163,340,705 steps (event 6,086,451), and at C(337,840,637) after 725,814,446,706,290,623 steps. The word-level engine agrees with a plain C simulator at all 24,646 events of the first 1010 steps (step count and CRC of the tape).

py/closure/cycle.py reach, py/closure/check_events.py, c/events.c

Neighbouring classes halt

The same pattern with 61 words in the left block halts for every odd r ≥ 65, after 1,772,276 + 5,220 (r − 65) steps (confirmed by plain simulation for r = 65, 67, 71); C(r) with r even ≥ 64 halts at its 21,362,421st event. So the real run is safe only because of the exact orbit it is on.

py/closure/classes.py

Independent check of the growth cycle

A second accelerated simulator, written from scratch without reading the first (verify/sim3.cpp, validated against plain simulation to 1010 steps), lands exactly on C(16,797,709) at step 1,818,198,163,340,705 from blank tape, and takes C(r) exactly to C(r + 321,042,928) at the predicted step for r = 65, 67, …, 85 and r = 16,797,709. It also confirms that C(r) halts for the even r tried (the halting transition is one step after the count stated in the notes: that count excludes the halting step). It checks listed values only; “for every odd r” is the Lean theorem grow_cyc.

verify/README.md, verify/run_all.sh

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/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/lean/check.sh      # Machine, Blank, Rules, Phases, Cycle, Exec, ExecData, Arrive, Period, Replay (1 min)
python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/replay/gen.py --check      # the model of the Lean executor: tables, move counts, events and steps as claimed (40 s)
python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/closure/cycle.py check      # the growth cycle from the claim alone (20 s)
python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/closure/cycle.py reach      # blank tape reaches C(16797709) (5 s)
python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/closure/cycle.py instance   # numeric runs from C(65), C(67), C(79) (40 s)
python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/closure/cycle.py mutate     # 17 defects, all reported (6 min)
python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/closure/classes.py          # neighbouring classes (4 min)
gcc -O2 -o events holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/c/events.c && ./events 1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA 10000000000 > ev10.txt && python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/closure/check_events.py ev10.txt --plain
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA 1000000000
holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/verify/run_all.sh      # independent simulator: arrival and one period for several r (about 2 min)