Busy Beaver Explorer / 1RB1RA_1LC1LD / explained

A six-state Busy Beaver holdout · status as of 1 November 2026

Does this machine ever halt?

1RB1RA_1LC1LD_1LD0LB_1RE0RF_---1RD_1RA1RB

Nobody knows. Started on a blank tape, this Turing machine has run for more than a trillion steps without stopping. This page shows how its run is organised, what has been proved about it in Lean, what has only been computed, and exactly where the two gaps are that stand between the current results and an answer.

native_decide1012 stepsNo halt. 8,257 passes of the pass map, each pass and its step count kernel-checked; only the evaluation trusts the compiler.
KernelHalts only at the right edgeA closed tape language shows a halt can only happen when E steps onto the blank region past everything written.
Kernel, if pre stopsTwo ways to haltFrom a safe pass start a halt needs case A (a last block 3 after a block ≥ 6) or case B (a last block 6 with offset 0).
OpenTwo gapsBounded left-end growth inside a recursive pass, and whether the last block can ever descend to 9.
Kernel proved in Lean, checked by the kernel only
native_decide proved in Lean, one evaluation trusts the compiler
Computed C or Python, tested but not proved
Heuristic evidence and estimates
Open not known
1 · The machine

Six states, two symbols, one halting transition

Each entry says what to write, which way to move and which state to enter. The only missing entry is E reading 0, so the machine halts exactly when it is in E on a 0. E is entered only from D reading a 0 (write 1, move right), so a halt is the moment D reads a 0 with another 0 to its right.

A sweeps right over ones and turns at the first 0. B and C carry the head left. That asymmetry is the shape of everything below: long sweeps to the right edge, and work done on the way back.

statereads 0reads 1
A1 R B1 R A
B1 L C1 L D
C1 L D0 L B
D1 R E0 R F
Ehalt1 R D
F1 R A1 R B

Kernel The machine stops exactly in E on a 0, and D>0 0 halts on the next step whatever the rest of the tape.

step_none_iff, halt_shape · lean/Blank.lean

Kernel A closed tape language with windows of three cells (245 abstract configurations, checked by decide +kernel) covers every configuration of the run from blank tape. Past the head, two 0s in a row occur only in the blank region, so the machine halts if and only if E reaches the blank region at the right edge. D at the left end always has a 1 to its right, but that is forced by the step that brings it there.

reach_inv, right_no_double_zero, d_zero_zero, halts_iff_edge, d_left_end · lean/Edge.lean, lean/EdgeCert.lean
2 · Watch it run

The tape from blank, step by step

This is the real machine, simulated in your browser. Step it one move at a time, or jump to the next pass start: the moment A stands on a fresh blank cell right of everything written. At every pass start the tape is blocks of ones separated by single 0s, and those block lengths are all that matter.

step 0state A cells visited 1ones 0passes 0
Above: 25 cells around the head (dark = 1). Below it: the whole visited tape, squeezed to the width of the panel; the orange tick is the head.
1headpass start
Space-time diagram of the first 1,700 steps, eight passes: time runs to the right, the tape runs top (left end) to bottom (right end). Each zigzag is a pass: a slow walk left converting the last block, then a sweep back right that ends one cell further out. The vertical marker follows the simulator above.

Kernel No halt in the first 20,000 steps, and the tape after 46 steps is 1^2 0 1^5 A>0.

blank_runs_20000, blank_at_46 · lean/Blank.lean

Computed No halt in 1011 steps with the C simulator (12,410 ones at the end). The width grows roughly like √(t/250).

tools/c/tmrun.c · notes/LAB_NOTES.md
3 · Blocks and passes

A pass, read as a map on block lengths

Write a pass start as 1^b₁ 0 1^b₂ 0 … 0 1^bₖ A>0. Three steps later B starts converting the last block from the right, three cells at a time (111 B> 1 0 becomes B> 1 0 101). What happens at the left end of the last block depends on its length mod 3.

last block bnext pass startwhat happensLean
1haltsD reads 0 0 at the right endK_zero_halts
4… x+6, 1halts on the next passkA0
3m+1, m ≥ 2… x+6+2⌊(m−1)/2⌋, 2m−1shrinks: b+5 becomes exactly ⅔(b+5)kA, kB
3m+2… d+2+2⌈m/2⌉, x+2m+3a carry crosses the block to the left; the last block becomes at least x+3kC, kD
3jrecursivethe converter carries on into the blocks further leftastep, pass
x is the block left of the last, d the one before it; a missing block counts as 0.

Kernel The closed form above is what the machine does for every block length and every tape further left. When the last block is a multiple of 3, the pass is followed by a machine on lists of numbers (astep, 25 kinds of step, each proved sound). Together they give pass, one pass for every last block: whatever it returns, next pass start or halt, the machine does. That pass always finishes is not proved.

next_sound, astep_sound, pass_sound, passes_sound · lean/Macro.lean, lean/Recur.lean

Kernel From blank tape: 2 2 → 2 5 → 4 7 → 10 3, and 100 more passes reach 1^162 0 1^206 A>0 at step 2,065,482. With step counts carried along (passC), the fourth pass start is at step 183.

blank_passes, blank_passes_104, blank_passesC · lean/Macro.lean, lean/Recur.lean, lean/Count.lean

native_decide 8,257 passes from 1^10 0 1^3 reach 1^11866 0 1^17246 A>0 at step 1,000,110,302,407, so no halt in the first 1012 steps. Each pass and its step count is kernel-checked; only that one long evaluation trusts the compiler.

blank_reaches_1e12, blank_runs_1e12 · lean/Count.lean

Computed The pass map agrees with every pass start of the raw run: all 1,786 in the first 1010 steps (Python), and in step number and blocks with all 3,843 to 1011 (C). The pass map in this page is a JavaScript transcription of the Python mirror of pass. It agrees with the Python on 3,000 random lists and with the in-page raw simulator on the first 118 passes, and after 8,257 passes from 10 3 it lands on the same start as Lean, 11866 17246.

py/macro.py check-full · tools/c/tmrun.c
4 · Pass explorer

Follow any pass start

Type a list of block lengths (left to right, last block last) and run the full pass map. Each row tags the start: safe or good (defined in section 6), and the kind of pass that follows. Recursive passes show their offset c and the number u of supply words pre took. The presets include every halting start named in the Lean files.

Presets:
5 · The recursive pass

A last block 3j becomes 2j + c

When the last block is a multiple of 3 the converter does not stop at its left end: it runs on into the blocks further left, and on the way back it handles a stream of short words 0 1^k. The pass then ends in a regular loop over the words 0 1 1: every two words add 4 to one block and 2 to its neighbour, and each word left over adds 2 to the last block.

The irregular part before that loop never reads past the words in front of it, so it is the same for every j. Lean runs it once (pre), taking words 0 1 1 from an unbounded supply as needed. It takes u of them and stops with p still ahead and a block a under the head. Then for every j ≥ u the next last block is 2j + c, with c = a + 2p − 2u depending only on the blocks to the left.

Kernel The final loop, pre once for all j, and the formula 2j + c (recur_sound). For x = 2, in closed form for every list to the left: c = −1, so …, 2, 3 becomes a last block 1 and halts, and a last block of 6 or more after a 2 keeps a good start good.

tail_end, pre_sound, recur_sound, recur_two, recur_two_three_halts, recur_two_good · lean/Formula.lean

Kernel, if pre stops For every list of blocks ≥ 2, of any length: c ≥ −1, and c ≥ 0 unless x = 2; u ≤ 2; the blocks left behind are ≥ 2. The proof is an abstract interpretation of the block machine (numbers up to 3 exact, larger ones by residue mod 3) whose 4,463 reachable descriptions the kernel checks in 127 pieces. So for j ≥ 2, a good list with last block 3j passes to blocks ≥ 2 with last block ≥ 2j − 1.

offset_bound, recur_next, check_ok · lean/Offset.lean, lean/OffsetData.lean

Kernel pre never gets stuck on a good list, and the cells right of the head, read from the right end, go down in dictionary order at every step. So if the run keeps at most N cells, pre stops within 4·3N steps. The bound N itself is the first open gap (section 9).

astep_key, prog_ok, pre_stops, recur_next_bounded · lean/Finish.lean, lean/Stops.lean

Computed With x ≠ 2, c = 0 exactly when pre takes two supply words (all 2,743 lists of 1 to 3 blocks of 2..15). For x = 6r + 5, c = 4r + 2 on every list tried.

py/blocks.py caseb, offsets
6 · Good and safe starts

Where a halt could still come from

A pass start is good if every block is at least 2 and the last block is neither 1 nor 4. Covered passes keep good starts good (Kernel next_good), so trouble can only come from recursive passes. But good is not enough: 2 2 3 and 3 6 are good and halt.

A pass start is safe if it is good, has at least two blocks, and has a last block 3 only after a block of at least 6. The run reaches the safe start 10 3 (blank_safe). Then, assuming pre stops, every route out of safety is accounted for:

Safe pass start, last block b
↓
b ≠ 3, 6
next start is safe Kernel
safe_pass
b = 6 after a 2
gives a last block 3 after a block ≥ 10, safe Kernel
six_after_two
Case B: b = 6 after x ≠ 2
next last block 4 + c with c ≥ 0. If c = 0: 4 → 1 → halt. Otherwise safe. Open
six_pass
Case A: b = 3 after x ≥ 6
never unsafe in 55,700 lists tried: c is 0 with two supply words, or ≥ 3 Computed
py/blocks.py chain

Kernel, if pre stops From a safe start with last block other than 3 and 6, the next start is safe, its last block is at least two thirds of the old one less 5/3, and it is 6 only if the old one was 9, or 2 after a block 3. So case B is entered only at the end of a descent through 9, falling by at most a factor 3/2 a pass.

safe_pass_shrink · lean/CaseB.lean

Kernel No lower bound on the last block by the size of the tape is kept by every pass: a covered pass from a last block 1 mod 3 shrinks it while every other block stays or grows. Sizes alone cannot rule out the descent.

descent_step, no_total_bound · lean/Bound.lean
7 · Halting starts

Starts that do halt, and the descent they share

These are not on the run. They are small pass starts that look like the run's (safe, even leftmost block) and still halt, which is why no condition on a single pass start can settle the question. Each is evaluated by the kernel. Load any of them in the explorer above.

startpath to the haltLean
3 63 6 → 2 7 4 → 2 13 1 → haltthree_six_halts Kernel
2 2 32 2 3 → 10 1 → halttwo_two_three_halts Kernel
8 68 6 → 2 11 4 → 2 17 1 → haltcase B example (notes) Computed
16 1616 16 → 26 9 → 6 27 6 → 14 27 4 → 14 33 1 → haltsixteen_halts Kernel
314 54314 54 → 70 265 36 → 76 277 24 → 80 287 16 → 80 297 9 → 94 291 6 → 22 175 194 4 → 22 175 200 1 → haltchain_54_halts Kernel

The descent chain

9recursive,
c = 0
6recursive,
c = 0 (case B)
4covered
kA0
1covered
K_zero_halts
halt

Every halting start found ends this way (all 63 safe starts x b with x even below 400 and b below 300 that halt within 12 passes go through case B, Computed). To get to 9 the last block must come down a staircase: each covered pass from a block 1 mod 3 takes b + 5 to ⅔(b + 5), and k such steps in a row need 3k to divide b + 5. 314 54 shows a full descent: 54 → 36 → 24 → 16 → 9 → 6 → 4 → 1.

So the question of halting has become a question about digits: does the run ever produce a small last block whose base-3 digits line up for a long enough staircase? That is the Collatz-like core of this machine.

8 · The run so far

The last block stays far from 9

Every pass start of the run from 10 3 to step 1012, computed with the full pass map. The last block wanders but its lows climb with the tape; the dashed line marks 9, the entry to case B.

last blocktotal ones on the tape
Log scale. Hover for the pass start.

Descents by length

A descent is a maximal run of passes that each shrink the last block. Each further step happens with probability about 0.4.

Computed All 8,257 pass starts to 1012 steps are good, case B is never reached, offset 0 occurs at most 3 recursive passes in a row, and the smallest last block from pass 2,000 on is 375. The deepest descent, from pass 4,151, goes 9,715 → 375 in 8 passes.

py/blocks.py caseb, descents

Computed Residues do not separate the run from the halting starts: mod 27 the run's last two blocks take 728 of the 729 pairs, and every known halting start shares its pair with some pass start of the run mod 54.

py/blocks.py residues

Heuristic Coming down from b to 9 takes about log(b/9)/log(3/2) descent steps, so it happens with probability about (b/9)−2.26. The total grows linearly in the passes and the median last block is about 0.65 of it, so the chance at pass t falls like t−2.26 and the sum converges. Evidence, not proof, that the run never reaches case B.

notes/LAB_NOTES.md, 1 November
9 · Inside a recursive pass

The carry, and how the tape grows at the left end

Watch pre only at the moments A stands with no ones under the head. Between two such moments it eats exactly the first two words. Call a word other than 2 irregular. Only the pair 1 2 writes new words: the converter carries left over the blocks that are 1 mod 3, turning each block 3jᵢ + 1 into a word 1 followed by jᵢ words 2, and stops at the first block that is not 1 mod 3.

the carry stops atblocks afterwords writtentoken countLean
a block 3m + 3c+3, d+22^m, carried words, 3+1 −[c≠0] −[d≠0]row_zero
a block 3m + 83, c+62^m, carried words, 3+1 −[c≠0]row_two
a block 52, c+6 (or 4, c+6)farthest word 1 used up−1 unless c = 0row_five, row_five_nil
a block 2c+6, a new carrycontinues as Drow_small, row_small_nil
past the leftmost block2, 2 (new)2^j, carried words, 3+1 (growth)row_end
The pairs that write no words: 2 2 (the loop; blocks gain 4 and 2), 2 1 and 2 3 (remove the irregular word), 3 2 (pushes a block 4), 3 1 (a block 3), 3 3 (a block 5). Tokens are irregular words plus nonzero blocks.

Kernel Every rule in the table, for every block and word length, with the exact token count after it. The count goes up only at the rows that write a block past the leftmost one, which is exactly where the tape grows.

carry, carry_start, row_zero, row_two, row_end, row_five, row_small, two_one, two_three, three_two, three_one, three_three, *_tokens · lean/Tokens.lean

Left-end growth

The tape grows at the left only when the carry runs off the left end, after every block between the head and the end has become words. Each such growth step can leave the tape a cell longer, and they can come several in a row. If they are finitely many, the cells stay bounded between them and pre_stops applies, so bounding them is the whole of the first gap.

Kernel The two-block cycle shrinks. A growth through row_two leaves blocks 3, 6; if 2t words 2 and then 1 2 follow with t = 3s + 1, the loop makes the blocks 4t+3, 2t+6, the carry grows the tape again, and the state returns to 3, 6 with t replaced by s = (t − 1)/3. So that cycle ends within log₃ t + 1 rounds.

cycle36 · lean/Tokens.lean

Computed The number of growth steps in a pass is at most the starting token count plus 2 (20,000 random lists and three hill climbs). The head's drift past the left end grows with the number of blocks: a hill climb finds 6 cells with 4 blocks, 9 with 8, 11 with 12, 13 with 24. On the run, the 582 recursive passes to 1010 steps drift at most 6 cells.

py/tokens.py, py/macro.py reach

Computed On the run, new blocks appear at the left end as a ladder 2 11 10 30 90 270 810 …, each block three times the last from 30 on, which later passes absorb from the right.

notes/LAB_NOTES.md, 31 October

Heuristic No potential linear in counts of words and blocks can work: linear programs over thousands of kinds of step are infeasible, and every multiset or dictionary order tried goes up at the growth steps. A proof has to follow the lengths of the runs of 2s, as cycle36 does for one cycle.

notes/LAB_NOTES.md, 1 November
10 · The open gaps

What stands between these results and an answer

Gap 1 · Bounded left-end growth

Show that inside a recursive pass the head does not drift left without bound, equivalently that there are finitely many growth steps. With it, every recursive pass finishes, pre always stops, and every result marked "if pre stops" becomes unconditional: c ≥ −1 for every list, the safe-start reduction, and safe_pass_shrink. The computed bound "growth steps ≤ starting tokens + 2" is the candidate, and cycle36 is the first piece of it.

Gap 2 · The Collatz-like descent

Case B: does the run ever bring the last block down to 9 and then to 6 with offset 0? No condition on a bounded number of blocks decides it (16 16, 314 54), sizes alone cannot (no_total_bound), and residues mod 54 cannot. On the run the chance of such a descent falls fast enough that its sum converges, which is evidence, not proof.

Case A (a last block 3 after a block ≥ 6 followed by an unsafe start) is also open in Lean, but never happens in 55,700 lists tried; a proof would need the abstraction to keep x ≥ 6 and separate c = 0 from c ≥ 3.

Open Whether the machine halts from blank tape. If gap 1 is closed and case A is proved, the run halts if and only if it reaches case B.

11 · Ledger

Every result, by what it rests on

The proof-status page has every result with its theorem names, built from bb6-1RB1RA_1LC1LD/status.json.

Source: the repository fractal-geometry-explorer/busy-beaver-explorer, folder bb6-1RB1RA_1LC1LD (README, status.json, notes/LAB_NOTES.md, lean/Axioms.lean), through pull request #166. To check: bb6-1RB1RA_1LC1LD/lean/check.sh with Lean 4.34.0, then python3 bb6-1RB1RA_1LC1LD/tests/test_machine.py.