Busy Beaver Explorer / holdouts / 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC

What is known about 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC

1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC

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 was one of the holdouts left open by the bbchallenge project. It does not halt from blank tape: Lean proves it, with a symbolic checker that the kernel proves sound, the round trips evaluated by the kernel and the long runs by compiled code (native_decide). This page lists what has been established about it, sorted by what each result rests on.

Status as of 8 November 2026.

In short

It never halts. Lean proves nonhalting: from blank tape the machine reaches one of 62 tape templates and moves from template to template forever. The 62 round trips are checked by the kernel; the start and the 62 ends of an epoch (2.5 million symbolic moves) by native_decide.

What it does. Each time B reaches the left end the tape reads B> 00 (01)a 000 (01)b 000 …, a list of counts separated by short words. The rightward sweep turns 010101 into 011001 and the leftward sweep turns it back. Each round trip takes 3 from a, while the end of the list runs through one of four periodic patterns (periods 15, 22, 16 and 9 round trips) and b gains 99, 141, 99 or 57 per period. When a is used up, b takes its place and a new, longer epoch begins: the first counts of successive epochs are 4, 12, 20, 38, 68, 122, 240, 484, 1002, 2104, 4375, ….

Why it cannot halt. Only D reading a 0 halts, after C>1 0. Every round trip of every pattern and every way an epoch can end has been checked as a symbolic run with the counts as variables, and each lands on a template again; a potential on the counts shows that an epoch always ends with the second count large enough for those runs.

Other proofs and outside reports

Also proved in Coq

A second proof assistant checks the same result: H36670.nonhalt : ~ halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in tools/coq/busycoq/H36670. 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 (a 668-line checker for tapes with two blocks of unknown length and a 58-line file with four seed tapes; Coq 8.20.1 checks it in about 25 seconds) is on a branch of our fork of busycoq, ready to be proposed upstream: bb6-nonhalt-1RB0LF_1LC0LA_1RA0RD_HHH1RE_1LA1RC_0LB0RC.

Community label

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

Shift rules

B with a 1 behind it turns each 010101 into 011001 going right (14 steps a copy); C with 110 ahead turns each 011001 back into 010101 going left (22 steps a copy).

sweep_right, sweep_left, lean/Rules.lean

The halting situations

C>1 0 halts after one step, E>1 1 0 and F>1 1 0 after two, D>1 1 1 0 after three.

halt_C, halt_E, halt_F, halt_D, lean/Rules.lean

A verified symbolic checker

lean/SymCheck.lean: configurations whose tape is a list of cells and runs wn with n linear in some variables; auto finds the moves itself (a run crossed by a shift rule found on the spot, else one step) and compares normal forms at the left end. auto_reach proves that a successful check means the machine makes that run, for every value of the variables.

auto_reach, lean/SymCheck.lean

The 62 round trips

Each phase template B> 00 (01)3k+4 000 (01)3j+β rest at [k+1, j] reaches the next phase at [k, j + dj] (200 to 2,500 symbolic moves each), evaluated by the kernel. The tables also show that j + 2k + pot never decreases in a round and is at least 215 after an epoch.

round_0 … round_61, tables_ok, lean/Cert.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 62 ends of an epoch

Each template at [0, j+200] reaches a template again, with the old second count as the new first (4,200 to 127,000 symbolic moves each, 2.5 million in all), evaluated by compiled code; the kernel runs out of memory on runs this long.

ends_ok, lean/Cert.lean

The start

From blank tape the machine reaches template 31 (pattern R1, phase 16) with first count 118 and second 496, at step 1,277,431 (147,895 symbolic moves).

start_ok, lean/Cert.lean

It does not halt from blank tape

The invariant “at a template with j + 2k + pot ≥ 215” holds at the start and is restored after a round or an end, each taking at least one step, so the run is defined for every length. #print axioms lists propext, Quot.sound and the two native_decide axioms.

nonhalting, lean/Cert.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 39,660 cells have been visited and 19,822 of them hold a 1.

holdouts/triage.json

D never reads a 0 in 2·108 steps

In the first 2·108 steps the machine is in state D 22,202,037 times, every time on a 1: the halting transition D0 is never close to firing in a way the run shows.

c/visits.c

Related holdouts

The same table as 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA up to renaming, 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

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.497). 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.507).

tools/py/bbtools/triage.py

Four regimes, growing epochs

How the templates were found: along the run, the list at the left end settles each epoch into one of four periodic patterns of period 15, 22, 16 or 9 round trips, in which the first count drops by 3 per trip and the second grows by 99, 141, 99 or 57 per period. Concrete simulations from every phase and residue return to a pattern.

py/regimes.py, py/endcases.py

open Open

Nothing yet.

Check it yourself

. /etc/profile.d/lean.sh      # after scripts/setup-lean.sh
holdouts/1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC/lean/check.sh
python3 holdouts/1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC/py/cert.py   # rewrites lean/Tables.lean
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC 1000000000