Busy Beaver Explorer / 1RB1RA_1LC1LD / explained
A six-state Busy Beaver holdout · status as of 1 November 20261RB1RA_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.
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).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.
| state | reads 0 | reads 1 |
|---|---|---|
| A | 1 R B | 1 R A |
| B | 1 L C | 1 L D |
| C | 1 L D | 0 L B |
| D | 1 R E | 0 R F |
| E | halt | 1 R D |
| F | 1 R A | 1 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.
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.
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.
Kernel No halt in the first 20,000 steps, and the tape after 46 steps is 1^2 0 1^5 A>0.
Computed No halt in 1011 steps with the C simulator (12,410 ones at the end). The width grows roughly like √(t/250).
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 b | next pass start | what happens | Lean |
|---|---|---|---|
| 1 | halts | D reads 0 0 at the right end | K_zero_halts |
| 4 | … x+6, 1 | halts on the next pass | kA0 |
| 3m+1, m ≥ 2 | … x+6+2⌊(m−1)/2⌋, 2m−1 | shrinks: b+5 becomes exactly ⅔(b+5) | kA, kB |
| 3m+2 | … d+2+2⌈m/2⌉, x+2m+3 | a carry crosses the block to the left; the last block becomes at least x+3 | kC, kD |
| 3j | recursive | the converter carries on into the blocks further left | astep, pass |
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.
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.
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.
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.
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.
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.
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.
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).
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.
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:
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.
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.
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.
| start | path to the halt | Lean |
|---|---|---|
| 3 6 | 3 6 → 2 7 4 → 2 13 1 → halt | three_six_halts Kernel |
| 2 2 3 | 2 2 3 → 10 1 → halt | two_two_three_halts Kernel |
| 8 6 | 8 6 → 2 11 4 → 2 17 1 → halt | case B example (notes) Computed |
| 16 16 | 16 16 → 26 9 → 6 27 6 → 14 27 4 → 14 33 1 → halt | sixteen_halts Kernel |
| 314 54 | 314 54 → 70 265 36 → 76 277 24 → 80 287 16 → 80 297 9 → 94 291 6 → 22 175 194 4 → 22 175 200 1 → halt | chain_54_halts Kernel |
kA0
1coveredK_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.
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.
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.
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.
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.
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 at | blocks after | words written | token count | Lean |
|---|---|---|---|---|
| a block 3m + 3 | c+3, d+2 | 2^m, carried words, 3 | +1 −[c≠0] −[d≠0] | row_zero |
| a block 3m + 8 | 3, c+6 | 2^m, carried words, 3 | +1 −[c≠0] | row_two |
| a block 5 | 2, c+6 (or 4, c+6) | farthest word 1 used up | −1 unless c = 0 | row_five, row_five_nil |
| a block 2 | c+6, a new carry | continues as D | row_small, row_small_nil | |
| past the leftmost block | 2, 2 (new) | 2^j, carried words, 3 | +1 (growth) | row_end |
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.
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.
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.
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.
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.
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.
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.
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.