Busy Beaver Explorer / 1RB0LF_1RC0LB
What is known about 1RB0LF_1RC0LB, and what is open
1RB0LF_1RC0LB_1RD1RB_1RE1RF_1LA---_0RC1LA
Nobody knows whether this six-state, two-symbol Turing machine halts when started on a blank tape. This page tracks what has been established about it, sorted by what each result rests on.
The run is a sequence of passes: the head fills a sparse region into solid 1s moving right, and turns solid blocks back into alternating cells moving left. Lean proves which passes halt, and that from pass start to pass start the run is a macro machine on a stack and a list of segment and gap lengths; the machine halts only if that macro machine gets stuck.
Status as of 6 November 2026.
In short
The question is open. Lean proves no halt in the first 20,000 steps by the kernel alone and in the first 108 steps with native_decide (through the macro machine); the C simulator finds no halt in the first 1010 steps.
Where a halt would come from. Every rightward run is a pass that crosses gaps (runs of 0s between two 1s) of length 1 and 2 and stops at the first other gap. Lean proves that the pass halts exactly when that gap has length 3 (pass_outcome, kernel).
Why it has not halted. Lean proves that the run is a macro machine on lists of numbers, and that the machine halts only if the macro machine gets stuck. That needs two 1s side by side next to an empty segment, which only odd numbers can bring about; in the run they are rare (at most 4 at a time), and the macro machine has never been stuck in 1010 steps. Is that luck or structure? Configurations one even number away from the run's do get stuck, and per flip the run looks just like them: at their stuck rate it would have got stuck with probability about 0.17 so far. No structural reason for it to stay unstuck has shown up.
What each result rests on
kernel Proved in Lean, kernel-checked
The halting configurations
The machine stops exactly in state E reading a 1, and D>0 1 halts after one more ordinary step, whatever the rest of the tape.
step_none_iff, halt_shape, lean/Blank.lean
No halt in the first 20,000 steps
The list simulator of the shared library, proved to agree with the machine's semantics, runs 20,000 steps from blank tape without a halt, evaluated by Lean's kernel. At step 63 the tape is 0 1^2 0 1^4 C>0 (blank_at_63).
blank_runs_20000, blank_at_63, lean/Blank.lean
Which passes halt
A pass starts when F or B reads a 0 and moves right; C then crosses every gap of length 1 or 2 (by induction over any list of them). The first gap of another length ends the pass: a gap of 3 halts, a gap of 4 or more turns left at E, two 1s side by side turn left at B or F. So a pass halts exactly when the first gap it meets that is not 1 or 2 has length 3.
pass, pass_outcome, start_F, start_B, lean/Pass.lean
The leftward pieces
A and F turn 1^(2k) A>1 into A>1 (1 0)^k; B erases 1^k; at the 0 left of a block an odd block starts a pass and an even block starts B erasing the block before it.
sweep, sweep_end_odd, sweep_end_even, erase, erase_end, lean/Pass.lean
The macro machine
At every pass start the tape is a stack of solid blocks 1^(2s+2) separated by single 0s, the head on a gap of 2h+2 cells, and a word of segments (0 1)^m and gaps 0^(2g) 1. A function mstep on these numbers gives the next pass start, and Lean proves the machine goes there, for all values of the parameters. mstep fails only at a gap g = 0 (two 1s side by side) next to an empty segment. So if the macro machine never gets stuck from the configuration after 12 steps, the machine never halts.
mstep_sound, blank_to_M0, no_halt_of_macro, lean/Macro.lean
A conserved counter
Read as a recursive program (the right stack of the two-stack form is a call stack), the macro machine keeps a sum Φ: the stack, plus the head gap, plus m + g − 1 for every segment m and gap g of the word. A pass that ends inside the word and a B step with a nonempty stack leave Φ unchanged; a pass that runs into the last segment adds 2 or 1; B with an empty stack takes 1 off. So Φ counts the passes that reach the right end, up to the rare steps at the left end. It does not by itself rule out getting stuck.
phi_interior, phi_end, phi_bottom, lean/Counter.lean
Odd numbers are the only danger, and come from the left end
If every stack entry, segment and gap n = g − 1 is even (the last segment may be anything), the macro machine is not stuck and stays all-even until B has an empty stack, for all values. The number of odd numbers goes up only when B has an empty stack, by exactly 1; otherwise a step keeps it, takes 2 off (two odd numbers cancel), or loses 1 at the last segment. So after t steps there are at most 1 + (visits to the left end) odd numbers; in the first 3·106 macro steps there are 38 such visits and never more than 3 odd numbers at once.
even_not_stuck, even_step, even_run, oddc_le, oddc_run, lean/Parity.lean
native Proved in Lean with native_decide
No halt in the first 10,000,000 steps
The same run for 107 steps, evaluated by compiled code.
blank_runs_10M, lean/Blank.lean
No halt in the first 108 steps, through the macro machine
Compiled evaluation runs the macro machine 108 steps from the pass start after 12 steps without getting stuck; the loop it runs is proved equal to mrun by the kernel, and mrun_sound turns it into at least 108 machine steps without a halt (in fact billions).
macro_runs_100M, blank_runs_macro_100M, mok_iff, lean/MacroRun.lean
trusted Computed, not proved
No halt in the first 1010 steps
The shared C simulator runs 1010 steps from blank tape without a halt; the tape then holds 313 ones and the head has visited 642 cells. The C simulator agrees with the Python reference simulator on the first 80 records of the run (a test).
tools/c/tmrun.c, tests/test_machine.py
No simple conserved quantity
No a·ones + b·pos + W[state] is conserved modulo 2 to 12, so a linear invariant like the first holdout's mod-3 count does not exist here.
tools/py/bbtools/invariants.py
No pass meets a gap of 3, and runs stay even
In the first 1010 steps there are 344,806,676 pass starts. At each one c/passes.c reads the cells ahead and finds the gap that will end the pass: never a gap of 3. And every run of 0s or 1s of length 3 or more between cells of the other symbol (away from the head) has even length: no odd run at any pass start. A Python version also runs each pass and checks the prediction against the machine (no mismatch in 106 steps).
c/passes.c, py/passes.py check, tests/test_passes.py
The run follows the macro machine
Run side by side with the machine, the macro machine predicts every one of the 344,806,676 pass starts in the first 1010 steps, cell for cell over the whole tape, and never gets stuck. Python agrees with C, and with the machine on all small configurations.
c/macro.c, py/macro.py check, tests/test_macro.py
The two-stack form does not get stuck in 5·1012 steps
The macro machine written as two stacks (each step one F pass and one B pass) does not get stuck in its first 5.1·1012 steps (of the order of 1014 to 1015 machine steps), run by a plain C simulator at about 4 s per 109 steps; a second C program that follows every frame by identity agrees up to 2·1011. Two flips leave a frame at value 0 (steps 204,719,421 and 2,084,922,784), both on frames with no turns left, and none happen after that; there are 1,923 R2 steps by 5.1·1012. The fast simulator equals the Python rules step by step for 20,000 steps and an exact memoized Python simulator after 2.5·108 steps; the frame-tracking one prints the same rows as the Python rules every 1000 steps for 3·105 steps; those rules are tested against mstep.
c/fastrun.c, c/twostack.c, py/accel.py, tests/test_accel.py, tests/test_macro.py
No small DFA closes the tape
One side of the tape abstracted by a DFA, the other kept exactly as a pushdown stack, reachability computed exactly by post* saturation: every DFA with at most 7 states, on either side, lets the abstraction reach a halt. Run-window languages on the tape do not close either. Tested sound on random small machines.
c/pds.c, py/pds.py, tests/test_pds.py, notes/LAB_NOTES.md
heuristic Evidence only
The tape grows very slowly
The visited width is 199 cells after 106 steps and 642 after 1010, so the time per new cell grows fast, far faster than for the other machines studied here. The left part of the tape holds blocks of 1s of even length separated by single 0s; the head reaches new cells on both sides.
py/blank.py records, notes/LAB_NOTES.md
Pass endings look like a binary counter
Almost every pass ends at a gap of length 4j + 2, and each j is about half as common as j − 1. In macro terms half of all passes are B passes, which end at their own head gap h = m + 2, where m is the last segment the F pass before crossed; h = 2, 4, 6, 8, … occur with frequencies halving exactly. In the macro machine the first nonzero gap is counted down by 2 per round and a segment just before it becomes a gap of its own size: a counter whose digits are the gaps. Not a proved description of the run.
py/macro.py stats, notes/LAB_NOTES.md
Only a few odd numbers
Odd numbers are born only at the left end of the tape (proved, above), and the left end is rare: 38 visits in the first 3·106 macro steps. In the run there are at most 4 odd numbers at a time, and F meets two 1s side by side only 546 times in 1010 steps (of 344,806,676 passes).
c/macro.c, notes/LAB_NOTES.md
Stuck configurations next to the run
Changing one to three even numbers of a configuration of the run by 2, with every parity kept, gets the macro machine stuck: 6 of 1,980 tries in Python, 20 of 1,500 in C with longer runs (108 to 109 steps). One example changes a single entry deep in the stack from 0 to 2. So whatever keeps the run from getting stuck depends on exact values, not on parities. Every stuck copy examined ends the same way: a frame created with value 2, a few frames above the end, flipped twice and then hit once more: a third flip, or its own odd countdown running out at value 0.
py/perturb.py, c/twostack.c perturb, notes/LAB_NOTES.md
The run is no safer than its perturbed copies
Per flip (an R2 step taking 1 from its caller) the run and its perturbed copies agree: 61–63 % of flips hit frames created with value 2, about 1 % are second flips, and the run's near-miss rate (2 in 1,181 flips by 1011 steps) is close to theirs (0.29 % over 124,075 flips). The copies get stuck about once per 6,200 flips (20 of 1,500 copies), so the run would have got stuck by 1011 steps with probability about 0.17. The copies do not relax back to safety (their rate stays flat for 108–109 steps after the change), their risk falls at most slowly with the run's age, and the run's flips do not thin out (about 200 per decade). If the run behaves like its copies, it gets stuck with chance 2 to 3 % per decade of steps: a halt is likely but astronomically late. This is a model, not a proof.
c/twostack.c, notes/LAB_NOTES.md
open Open
The macro machine never gets stuck
A description of where the odd numbers can be that the rules preserve and that excludes the two stuck cases. That would prove the machine never halts. An odd number has over a thousand distinct small neighbourhoods in the run, so the description is not tiny; window and pushdown languages over the macro numbers are the next tries. Any such description has to separate the run from configurations one even number away, which per flip behave like it and do get stuck.
notes/LAB_NOTES.md
Does it halt from blank tape?
Not known.
Check it yourself
bash scripts/setup-lean.sh # Lean 4.34.0, core only
. /etc/profile.d/lean.sh
bb6-1RB0LF_1RC0LB/lean/check.sh # the library, then Machine, Blank, Axioms (under a minute)
python3 bb6-1RB0LF_1RC0LB/tests/test_machine.py
bb6-1RB0LF_1RC0LB/lean/check.sh # also Macro.lean: mstep_sound, no_halt_of_macro
bb6-1RB0LF_1RC0LB/lean/check.sh # also Parity.lean: even configurations are safe, odd numbers come from the left end
python3 bb6-1RB0LF_1RC0LB/py/blank.py records 100000 60
gcc -O2 -o tmrun tools/c/tmrun.c && ./tmrun 1RB0LF_1RC0LB_1RD1RB_1RE1RF_1LA---_0RC1LA 10000000000
cd tools/py && python3 -m bbtools.invariants 1RB0LF_1RC0LB_1RD1RB_1RE1RF_1LA---_0RC1LA 12
python3 bb6-1RB0LF_1RC0LB/tests/test_passes.py
python3 bb6-1RB0LF_1RC0LB/py/passes.py check 1000000
gcc -O2 -o passes bb6-1RB0LF_1RC0LB/c/passes.c && ./passes 10000000000
python3 bb6-1RB0LF_1RC0LB/tests/test_macro.py
python3 bb6-1RB0LF_1RC0LB/py/macro.py show 40
python3 bb6-1RB0LF_1RC0LB/py/callstack.py check 1000000 # how the counter changes, by kind of step
gcc -O2 -o macro bb6-1RB0LF_1RC0LB/c/macro.c && ./macro 10000000000
python3 bb6-1RB0LF_1RC0LB/tests/test_pds.py
gcc -O2 -o pds bb6-1RB0LF_1RC0LB/c/pds.c && ./pds 6 L && ./pds 6 R # every DFA up to 6 states, about a minute each
gcc -O3 -o twostack bb6-1RB0LF_1RC0LB/c/twostack.c && ./twostack 10000000000 # about 90 s; TWOSTACK_VERBOSE=1 prints near misses
./twostack perturb 100000000 100000000 40 1 # 200 perturbed copies, 10^8 steps each, about 3 min
python3 bb6-1RB0LF_1RC0LB/tests/test_accel.py
gcc -O3 -o fastrun bb6-1RB0LF_1RC0LB/c/fastrun.c && ./fastrun run 1e12 - state.bin # about 70 minutes; resumable