Busy Beaver Explorer / holdouts / 1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---

What is known about 1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---

1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---

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

Nobody knows whether this six-state, two-symbol Turing machine halts when started on a blank tape: it is one of the holdouts left open by the bbchallenge project. This page lists what has been established about it, sorted by what each result rests on.

Status as of 9 November 2026.

In short

It does not halt, proved in Lean with native_decide for the long fixed computations. The configuration C k = 0^inf A> 0 (1010001000100)^k X, with X a fixed stretch of 222,182 cells, goes to C (k+1) in 184k + 3,029,040 steps for every k ≥ 1, and the run from blank tape reaches C 7 at step 16,730,681,219 (checked chunk by chunk with a block simulator proved correct in Lean). Theorem nonhalting in lean/Reach.lean.

Other proofs and outside reports

Also proved in Coq

A second proof assistant checks the same result: H32641.nonhalt : ~ halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---/coq. Coq 8.18 compiles it and Print Assumptions reports no axioms; the build log is next to the files.

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 (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 three symbolic passes over the blocks

With R any tape: 0^inf A> 0 (1010001000100)^(n+1) R reaches 0^inf (0101010010001)^(n+1) 1 B> R in 37n+38 steps; 0^inf (0101010010001)^(n+1) E> 0 R reaches 0^inf (0101010010001)^(n+1) 0 1 1 B> R in 92n+99 steps, passing after its first 55n+57 steps through 0^inf A> 0 1 0 (1000100010010)^(n+1) R at the left end (pass3). For every n and R.

pass1, pass2, pass3, lean/Pass.lean (generated by py/gen_pass.py with bbtools.symtm)

Runs on a window never look further left

A run on a finite window of cells that never moves left of the window (wsteps, a list simulator that fails when the head would leave the window) is a run of the machine with any tape at all on the left.

wsteps_over, wsteps_over1, wsteps_over3, lean/Window.lean

A block simulator, proved correct

The tape cut into blocks of 16 cells, and a table that says, for each state, block and side of entry, what the machine does in the block until the head leaves it. Each table entry is computed by a run on the block's cells that is proved to be a run of the machine whatever lies outside (brun_ok); the simulator msim looks up one entry per block crossing, and chkF_ok turns a successful check of a run of exactly t steps (macro steps, then single steps) into steps t ... = some ....

brun_ok, mstep_ok, msim_ok, chkF_ok, lean/Block.lean

The rightward sweep over the Q encoding is a block transducer

In state D, moving right, the head crosses each of the blocks 1000, 100100, 1001000, 10010100, 100101000 in state D without looking past it, so it crosses any word made of them block by block. A building block for the earlier phase; the period proof above does not use it.

dsweep, blk_cross, lean/Sweep.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 two excursions into X

Entering the fixed stretch X (222,182 cells, lean/Data.lean) from the blocks, the head comes back out after 1,517,479 steps in state E onto a 0, leaving a stretch r1; entering r1 the next time, it comes back after 1,511,551 steps, leaving a stretch that, with the two cells the last pass writes in front of it, is one more block followed by X again.

w1_ok, w2_ok, close, lean/Period.lean (native_decide)

One period of the bouncer, for every number of blocks

With C k = 0^inf A> 0 (1010001000100)^k X 0^inf: C (n+1) reaches C (n+2) in exactly 184n + 3,029,224 steps, for every n. So from any C (m+1) the machine runs for ever, and if the run from blank tape reaches some C (m+1), the machine does not halt.

period, not_halts_C, nonhalt_of_reach, lean/Period.lean

The run from blank tape reaches C 7 at step 16,730,681,219

The run is cut into eight chunks of about 2.09×109 steps at configurations dumped by the C simulator (lean/Bound.lean); each chunk is checked by the block simulator with native_decide (about 3 minutes each, lean/Chunk1.lean … lean/Chunk8.lean), the table by tblOk (20 s). The C simulator only proposes the boundaries; Lean checks every step between them. Chained: steps 16730681219 init = some (C 7).

chunk1 … chunk8, tblOk, reach_C7, lean/Reach.lean, generated by py/gen_reach.py

The machine never halts from blank tape

nonhalting : ¬ HaltsFromBlank, from reach_C7 and nonhalt_of_reach. It rests on Lean's kernel and on compiled evaluation for the native_decide facts (the two excursions into X, the closing equality, the block table and the eight chunks).

nonhalting, lean/Reach.lean

trusted Computed, not proved

No halt in 1011 steps

py/lturn.c runs 1011 steps without a halt and logs every 50th left turn; from sweep 49,300 on (step 1.68×1010) the left turn is the left end and the step counts of the turns follow a quadratic exactly (third differences 0): left end −2 cells per sweep, right end +4.5. At 1011 steps the tape spans cells −71,625 to 382,423.

py/lturn.c

heuristic Evidence only

Before the bouncer: a turning point that runs out and back in epochs

Up to step 1.67×1010 the leftward sweeps do not all reach the left end: the cell where they turn moves right, about 7 cells per sweep, until it meets the right end (sweeps 150, 650, 2,550, 9,500, 35,550, right end at 774, 3,024, 11,648, 42,923, 160,189 cells), then runs back to the left end (sweeps 250, 950, 3,600, 13,350, 49,300). Each epoch is about 3.7 times longer than the one before. After the fifth return the configuration is C 7 and the bouncer above takes over.

py/lturn.c, py/chart37.py

open Open

Nothing yet.

Check it yourself

. /etc/profile.d/lean.sh      # after scripts/setup-lean.sh
holdouts/1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---/lean/check.sh
python3 holdouts/1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---/py/gen_pass.py      # rewrites lean/Pass.lean
gcc -O2 -o dumpT holdouts/1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---/py/dumpT.c && ./dumpT 1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC--- 16730681219 | python3 holdouts/1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---/py/gen_data.py      # rewrites lean/Data.lean
./dumpT 1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC--- $(python3 holdouts/1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---/py/gen_reach.py --bounds) | python3 holdouts/1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---/py/gen_reach.py      # rewrites lean/Bound.lean, Chunk*.lean, Reach.lean
gcc -O2 -o lturn holdouts/1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---/py/lturn.c && ./lturn 1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC--- 100000000000 40 50 100000000 > lturn.txt