Busy Beaver Explorer / 1RB1RA_1LC1LD
What is known about 1RB1RA_1LC1LD, and what is open
1RB1RA_1LC1LD_1LD0LB_1RE0RF_---1RD_1RA1RB
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 machine is set up in Lean on the shared library, and the run from blank tape is simulated in Python, C and Lean. A closed tape language proved in Lean confines any halt to the right edge of the written tape. The macro structure of the run is not found yet. The run is a sequence of passes, each starting with A on the blank cell right of blocks of ones separated by single 0s; Lean proves the map from one pass start to the next for every last block: in closed form when the last block is not a multiple of 3, and, when it is, as a machine on lists of numbers whose every step is proved sound. The explainer runs the machine and the pass map in the browser.
Status as of 5 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 1012 steps with native_decide, by the pass map with step counts; the C simulator finds no halt in the first 1011 steps. These are floors, not the way to an answer.
Where a halt would come from. The only halting transition is E0, and E is entered only from D reading a 0, so the machine halts exactly when D reads a 0 with a 0 to its right. Lean proves that in the run from blank tape this can happen only at the right edge: past the head, two 0s in a row occur only in the blank region beyond everything written, so the machine halts if and only if E steps onto that blank region. At the left end D always has a 1 to its right, but that is forced by the step that brings D there, not a property of the run.
What each result rests on
kernel Proved in Lean, kernel-checked
The halting configurations
The machine stops exactly in state E reading a 0, and D>0 0 halts after one more ordinary step, whatever the rest of the tape.
step_none_iff, halt_shape, lean/Blank.lean
D at the left end has a 1 to its right
D is entered either from E reading 1, which leaves a 1 to D's left, or by a left move from B reading 1 or C reading 0, which writes a 1 to D's right. So D with a 0 on its left, in particular at the left end of the tape, always has a 1 on its right. This explains the observation from the long runs; it holds one step after any configuration, from any tape.
d_one_right, d_left_end, lean/Edge.lean
A halt can only happen at the right edge
A closed tape language with windows of three cells (an automaton on each side of the head and 245 abstract configurations, found by tools/py/bbtools/ctl.py and checked by decide in the kernel) covers every configuration of the run from blank tape. From it: to the right of the head cell, two 0s in a row occur only in the blank region beyond everything written; the halting shape D>0 0 occurs only with blank tape from D onward; and the machine halts from blank tape if and only if, at some step, it is in state E with blank tape from the head onward. The language does not constrain the left side, which may hold runs of 0s.
right_no_double_zero, d_zero_zero, halt_at_edge, halts_iff_edge, lean/Edge.lean, lean/EdgeCert.lean, tools/lean/TM/CTL.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 46 the tape is 1^2 0 1^5 A>0 (blank_at_46).
blank_runs_20000, blank_at_46, lean/Blank.lean
The pass map, when the last block is not a multiple of 3
Write a pass start as … 1^d 0 1^c 0 1^b A>0. Then the next pass start is … 1^d 0 1^(c + 6 + 2⌊(m−1)/2⌋) 0 1^(2m−1) A>0 when b = 3m + 1 (m ≥ 1), and … 1^(d + 2 + 2⌈m/2⌉) 0 1^(c + 2m + 3) A>0 when b = 3m + 2, for every block length and every tape further left (a missing block counts as 0). B converts the last block from the right, 111 into 101; at its left end the residue mod 3 decides where the cells go, and on the way back two blocks grow by 2 and 4 for every two converted words.
next, next_sound, lean/Macro.lean; the rules in lean/Rules.lean (generated by lean/rules.py)
A last block of 1 halts, and 4 halts one pass later
A pass start whose last block is 1 halts during that pass (D reads a 0 with a 0 to its right at the right end); a last block 4 gives a last block 1. So a pass start ending in 1^1 0 1^2 also halts, two passes later. No pass start in the first 1010 steps ends in 1 or 4.
K_zero_halts, kA0, halts_of_reaches, lean/Macro.lean
The first passes from blank tape
The run reaches the pass starts 1^2 0 1^2, 1^2 0 1^5, 1^4 0 1^7 and 1^10 0 1^3, the last three by the pass map; the fourth ends in a multiple of 3. Then 100 more passes by the full pass map below, 32 of them recursive, evaluated by the kernel: the run reaches the pass start 1^162 0 1^206 A>0 (after 2,065,482 steps).
blank_passes, lean/Macro.lean; blank_passes_104, lean/Recur.lean
The covered passes keep every block at least 2
Call a pass start good if every block is at least 2 and the last block is neither 1 nor 4 (1 halts on this pass, 4 on the next). Every pass the map above covers takes a good pass start to a good one, and so does any run of covered passes. So from a good pass start a halt needs a pass whose last block is a multiple of 3. On a covered pass the last block either shrinks, with the last block plus 5 becoming exactly two thirds of what it was (last block 1 mod 3), or becomes at least the block to its left plus 3 (last block 2 mod 3).
Good, next_good, nextIter_good, next_shrink, lean/Blocks.lean
The pass map for every last block
When the last block is a multiple of 3 the pass is followed by a machine on lists of numbers, astep: the state, the ones at the head, the blocks to the left and the words 0 1^k to the right. Each of its 25 kinds of step is proved to be what the real machine does, for every length and every tape around it, from 19 new tape rules in lean/Rules.lean (and one sweep of a block into the next word, by induction). With the closed form above this gives pass, one pass for every last block, and whatever it returns (the next pass start, or a halt) the machine really does. It is not proved that the block machine always finishes a pass (see the next item): where it meets a case it does not cover it returns nothing, and it never does so in the runs checked.
astep, astep_sound, pass, pass_sound, passes_sound, lean/Recur.lean
The block machine never goes round in circles
Read the cells from the head to the right end of the tape backwards, from the right end. Every step of the block machine that does not end the pass makes this list smaller in dictionary order (a 1 before a 0, a list before its extensions): either the head moves right past whole words, or the first word that changes, counting from the right end, gets longer. So the block machine never repeats a configuration, and if its head stays within N cells of the right end and it meets no case it does not cover, it ends the pass within 3N steps. That the head cannot drift left without bound is not proved; in every recursive pass computed it reaches a fixed distance past the left end of the tape that does not depend on the length of the last block.
astep_key, arun_finishes, pass_finishes, lean/Finish.lean; py/macro.py reach
The last block after a recursive pass: 2j + c
A recursive pass from … x, 3j turns the last block into the words 0, 0 1 and j words 0 1 1. Its end is a loop: from A before a block a with m words 0 1 1 ahead, every two words add 4 to a and 2 to the block left of it, and the next pass start has last block a + 2m, for every a, m and tape to the left. The block machine never reads past the words in front of it, so what comes before the loop is the same for every j: it is run once, with words 0 1 1 taken from an unbounded supply as needed (pre, u words taken, p still ahead when it stops), and then for every j ≥ u the next pass start has last block 2j + c with c = a + 2p − 2u, which depends only on the blocks to the left. For x = 2 this is closed form for every list to the left and every j: c = −1, so a last block 3 after a 2 becomes 1 and halts, and a last block of 6 or more after a 2 keeps a good pass start good. For every list of one to three blocks of 2 to 10 (819 lists) the kernel checks c ≥ −1, with −1 exactly when x = 2, for every j. That pre always stops is not proved.
tail_end, pre_sound, recur_sound, recur_two, recur_two_three_halts, recur_two_good, recur_small, lean/Formula.lean
c ≥ −1 for every list of blocks, if pre stops
For every list of blocks of at least 2 to the left of the last block, of any length: if pre stops, then c ≥ −1, and c ≥ 0 unless the block left of the last is 2; at most two words 0 1 1 are taken from the supply; and the blocks it leaves are all at least 2. So for every j ≥ 2 a good list with last block 3j passes to a list of blocks of at least 2 with last block at least 2j − 1. The proof describes configurations of the block machine abstractly: a number exactly if it is at most 3, otherwise by its residue mod 3; the first three blocks to the left and the first two words to the right explicitly, the rest by its shape (all 0; blocks of at least 2 then 0s; anything; and for the words, a run of words 1, 2, 3 in which every 1 is followed by a 2). Every step of pre is matched by an abstract step, and the kernel checks the 4,463 descriptions reachable from the starts, split into 127 pieces (about 70 seconds): none loses its description, and every one at which pre may stop has the bound. That pre always stops is not proved.
absAstep_sound, absNext_sound, pre_abs, check_ok, offset_bound, recur_next, lean/Offset.lean, lean/OffsetData.lean
pre never gets stuck, so it stops when the cells stay bounded
At each of the 4,463 abstract descriptions reachable from a list of blocks of at least 2, the block machine has a next step unless pre stops or takes a supply word there, and at most two supply words are ever taken (checked by the kernel on the tree). So the run of pre never meets a case the block machine does not cover. With the key that goes down at every step, this gives: if every configuration of the run keeps at most N cells (head offset plus the cells of the words), pre stops within 4·3N steps, and the next pass start has blocks of at least 2 and last block at least 2j − 1, with no further assumption. The abstract graph has cycles (two strongly connected parts of 1,838 descriptions each), so it does not by itself bound the cells; that the head does not drift left without bound remains open.
progA_sound, prog_ok, preR_inv, pre_stops, recur_next_bounded, lean/Stops.lean
Good starts do not stay good; a halt needs a last block 3 or 6
Goodness is not kept by every pass: 2 2 3 and 3 6 are good and halt (3 6 → 2 7 4 → 2 13 1). Call a pass start 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 10 3. If pre stops: a safe pass start with last block other than 3 and 6 is followed by a safe one (a covered pass makes a last block 3 only from 7, the block to its left gaining 6, and a recursive pass from 9 or more gives at least 5); a last block 6 after a 2 gives a last block 3 after a block of at least 10; and a last block 6 after any other block gives last block 4 + c with c ≥ 0, which halts if c = 0 and is safe otherwise. So, given that pre stops, a halt needs either a last block 3 after a block of at least 6 that is not followed by a safe start (case A), or a last block 6 with c = 0 (case B).
Safe, safe_pass, six_after_two, six_pass, three_six_halts, blank_safe, lean/Chain.lean
Case B needs the history: safe even starts that halt, and how fast the last block can fall
No condition on the pass start alone that safety and parity can express rules case B out: 16 16 and 314 54 are safe, every block even (as the leftmost block always is on the run), and both halt by case B (16 16 → 26 9 → 6 27 6 → 14 27 4 → 14 33 1, evaluated by the kernel). What a halt by case B needs, 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 last block was 9, or 2 after a block 3. So the last block must come down to 9 first, by at most a factor 3/2 a pass.
sixteen_halts, chain_54_halts, safe_pass_shrink, lean/CaseB.lean
No lower bound on the last block by the size of the tape is kept
A covered pass from a last block 1 mod 3 (at least 7) shrinks it to two thirds of it plus 5, less 5, while the block next to it grows and the rest stays, so the total grows by at least 2. Hence for any nondecreasing f, a good start whose last block is f(total) and 1 mod 3 passes to a good start below the bound. Ruling out a descent to 9 needs the residues that decide how long a descent lasts, not only sizes.
descent_step, no_total_bound, lean/Bound.lean
The pass map with step counts
Every rule of lean/Rules.lean states its exact number of steps, so the pass map can carry them: passC is pass returning, beside the next pass start (or a halt), the exact number of machine steps the pass takes, and passesC iterates it. Whatever they return, the machine does, in exactly that many steps. From blank tape the fourth pass start 1^10 0 1^3 A>0 is reached at step 183.
passC, passC_sound, passesC_sound, blank_passesC, lean/Count.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. Superseded by the pass map below, which goes to 1012.
blank_runs_10M, lean/Blank.lean
No halt in the first 1012 steps
The counted pass map, run from 1^10 0 1^3 for 8,257 passes and evaluated by compiled code (about 2.5 minutes), reaches the pass start 1^11866 0 1^17246 A>0 at step 1,000,110,302,407, so the run from blank tape does not halt in its first 1012 steps (and so not in the first 1010 or 1011). Only the evaluation trusts the compiler; that each pass is what the machine does, step count included, is kernel-checked. Every pass start on the way to 1011 steps (3,843 of them) agrees in step number and blocks with the C simulator.
blank_reaches_1e12, blank_runs_1e12, blank_runs_1e10, lean/Count.lean
trusted Computed, not proved
No halt in the first 1011 steps
The shared C simulator runs 1011 steps from blank tape without a halt (12,410 ones at the end; at 1010 steps 5,580 ones and 6,278 cells visited). The C simulator agrees with the Python reference simulator on the first 80 records of the run (a test). The Lean pass map now goes further (1012, above).
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 the mod-3 argument of the first holdout has no counterpart of this linear kind here.
tools/py/bbtools/invariants.py
The pass map agrees with the run to 1010 steps
In the first 1010 steps there are 1,786 pass starts, all of them blocks separated by single 0s, with at most 8 blocks and no block shorter than 2. The closed-form map agrees with the run on all 1,205 whose last block is not a multiple of 3. The full pass map pass of lean/Recur.lean, run by Lean on its own output from 1^10 0 1^3, gives all 1,782 later pass starts exactly, and its Python transcription gives all 1,786, the 581 recursive ones included. Both maps also agree with direct runs from 300 random block lists each that the run need not reach (tests).
py/macro.py check-full, tools/c/tmrun.c, tests/test_machine.py
Every pass start to 1011 steps is good
All 3,845 pass starts in the first 1011 steps have every block at least 2 and a last block other than 1 and 4. Blocks shorter than 10 occur only as the first block (2, 4, 6 or 8) or as the last block in the first dozen passes; after pass 156 (about 6·106 steps) the last block is always at least 22.
py/blocks.py run on tools/c/tmrun … at A R output
No halt in the first 1016 steps
The counted pass map of lean/Count.lean transcribed in Python, with the block machine on stacks and the costs of pre after one block and of the final loop in closed form, runs 178,000 passes from blank tape without a halt. It reproduces the step count that Lean proves for pass 8,257 (1,000,110,302,407) exactly.
py/twoblock.py run, tests/test_machine.py
Most of the run is a map on two numbers
87% of the first 95,333 pass starts are two blocks 1^x 0 1^b A>0, x always even; the others have at most 11 blocks. For one block x left of a last block 3j, pre is given in closed form (equal to the block machine for every x below 30,000): affine in x on each residue mod 18, except x ≡ 14 mod 18, where it follows the power of 3 in (x − 5)/9. So the pass map on two blocks is an explicit Collatz-like map on (x, b); the offset is 0 after an even block exactly when x ≡ 8 mod 18, or x ≡ 14 mod 18 and (x − 5)/9 without its factors 3 is 1 mod 6. Offset 0 occurs up to 6 recursive passes in a row; the smallest last block from pass 50,000 on is 1,787.
py/twoblock.py (pre1, verify), notes/LAB_NOTES.md (5 November)
Only a last block of 3 or 6 can break goodness
For a recursive pass from … x, 3j the new last block is 2j + c, where the offset c depends on the blocks to the left but not on j (proved, recur_sound), and is never below −1 (exactly −1 when x = 2; proved for x = 2 and for lists of up to 3 blocks of 2 to 10) and never 1 or 4. So with a last block of 9 or more the recursive pass also gives a good pass start, and every good list on which the next pass start is not good has last block 3 or 6: exhaustive over all lists of up to 3 blocks of 2 to 30 and up to 5 blocks of 2 to 12, and 20,000 random lists with blocks up to 200. Examples: 2 3 → 8 1, 5 3 → 8 4, 8 6 → 2 11 4. A last block 3 with a block of 6 or more to its left was always safe; a last block 3 from a covered pass always has one.
py/blocks.py exhaustive, random, offsets; tests/test_machine.py
Case B: offset 0 means two supply words, and the run stays far from it
With the block left of the last other than 2, the offset c is 0 exactly when pre takes two supply words, on all 2,743 lists of 1 to 3 blocks of 2..15. All 63 safe starts x b with x even below 400 and b below 300 that halt within 12 passes halt by case B, with b in {6, 9, 16, 24, 54}. Over the 8,257 pass starts to 1012 steps: the leftmost block is always even; offset 0 in 631 of 2,654 recursive passes, never more than 3 in a row; case B never reached; the smallest last block from pass 156 on is 53, from pass 2,000 on 375, and from pass 156 on the last block is at least 1.38 times the square root of the total number of ones.
py/blocks.py caseb, tests/test_machine.py
No residue invariant on the last two blocks separates the run from the halting starts
Over passes 156 to 8,256 of the run, the pairs (x mod M, b mod M) of the last block b and the block x left of it fill 728 of the 729 pairs mod 27, and the nine known safe even starts that halt by case B all share their pair with some pass start of the run for every M dividing 54 (seven of them mod 81, five mod 162). So no condition on these residues, with or without parity, holds on the run and fails on the halting starts: they differ from the run only in size and in the higher 3-adic digits.
py/blocks.py residues, notes/LAB_NOTES.md
heuristic Evidence only
The tape grows slowly and splits into two regions
The width grows like the cube root of the step count: after n passes the tape holds about 3.53·n ones and the step count is about 1.78·n3, so the width is about 2.91·t1/3 (6,300 cells after 1010 steps, 29,112 after 1012; between 2.89 and 2.93 at every thousandth pass to 1016 steps). An earlier fit near 1010 steps suggested a square root. During a pass the left part of the tape fills with blocks 1^2 0, with an occasional 1 0, and the head sweeps over it; the right part holds a few long blocks of 1s. The head reaches new cells mostly on the right.
py/blank.py records, py/twoblock.py run, notes/LAB_NOTES.md
Descents to 9 get rarer: the sum of their chances converges
On the run to 1012 steps there are 2,709 descents of the last block (maximal runs of passes each shrinking it), 1,454, 631, 416, 111, 59, 26, 9 and 3 of lengths 1 to 8: each further step about 0.4 likely, each shrinking the last block by about 2/3. Coming down from b to 9 then has chance about (b/9)−2.26; the total grows linearly in the passes and the median last block is about 0.65 of it, so this falls like t−2.26 in the pass number t, and the sum converges. Evidence, not proof, that case B is never reached.
py/blocks.py descents, notes/LAB_NOTES.md
The recursive case: a last block that is a multiple of 3
Then the converter does not stop at the left end of the last block: it carries on into the next block in a second mode (B reading 0 0), and that block's residue mod 3 decides again: 1 carries on further left, 0 and 2 turn back. So the routes form an infinite family (which the block machine of lean/Recur.lean follows one word at a time), one for each run of blocks that are 1 mod 3, and a route census over small cases would not be complete. In the first 1010 steps the converter crosses 0, 1, 2 and 3 extra blocks of 1 mod 3 in 400, 178, 3 and 1 of the 581 recursive passes. The rules for these steps are worked out symbolically but not yet put together in Lean.
notes/LAB_NOTES.md
No finite invariant: the danger is a shrinking chain
Both shrinking routes take the last block to about two thirds (covered: exactly, recursive: 2j + c). A last block 6 arises from a last block 9 with offset 0, which is common, and 9 from 15 or 16, and so on, so the pass starts that can reach a halt are not cut out by any condition on a bounded number of blocks: whether the run halts is a question about how these chains of residues line up. In the run the last block stays large: the fraction of pass starts after the first 300 with a last block below ε times the width is 0.33, 0.047, 0.0085 and 0.0006 for ε = 0.5, 0.2, 0.1, 0.05, and none below 0.036, falling faster than ε. If that continues, the expected number of last blocks of 9 or less is finite, which is evidence (not proof) that the run never halts.
notes/LAB_NOTES.md
open Open
That pre stops, and the bad last blocks
The new last block after a recursive pass is proved to be 2j + c with c depending only on the blocks to the left, c = −1 when x = 2, and c ≥ −1 for every list of blocks of at least 2 provided the part before the final loop (pre) stops (lean/Formula.lean, lean/Offset.lean). Open: that the head does not drift left without bound (proved equivalent to pre always stopping, since pre never gets stuck); case A of lean/Chain.lean, a last block 3 after a block of at least 6 (computed: always followed by a safe start, with c = 0 or c ≥ 3, over 55,700 lists, py/blocks.py chain); and case B, whether the run ever reaches a last block 6 with c = 0 (which does halt: 8 6 → 2 11 4; it is entered only through a last block 9 or 3 2, after a descent of the last block by at most 3/2 a pass, lean/CaseB.lean). Every other pass from a safe start is proved to give a safe start, given that pre stops.
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-1RB1RA_1LC1LD/lean/check.sh # the library, then Machine, Blank, EdgeCert, Edge, Rules, Macro, Blocks, Recur, Finish, Formula, Offset, OffsetData, Stops, Chain, CaseB, Bound, Count, Tokens, Axioms
python3 bb6-1RB1RA_1LC1LD/tests/test_machine.py
python3 bb6-1RB1RA_1LC1LD/py/blank.py records 100000 60
gcc -O2 -o tmrun tools/c/tmrun.c && ./tmrun 1RB1RA_1LC1LD_1LD0LB_1RE0RF_---1RD_1RA1RB 10000000000
python3 bb6-1RB1RA_1LC1LD/py/macro.py check 3000000 # the pass map against the run
./tmrun 1RB1RA_1LC1LD_1LD0LB_1RE0RF_---1RD_1RA1RB 10000000000 at A R 100000 | grep 'A>0$' > passes.txt && python3 bb6-1RB1RA_1LC1LD/py/macro.py check-full passes.txt
python3 bb6-1RB1RA_1LC1LD/py/blocks.py exhaustive 30 3 # good lists whose next pass start is not good: last block 3 or 6
python3 bb6-1RB1RA_1LC1LD/py/blocks.py chain 14 4 1 20000 # case A of lean/Chain.lean: a last block 3 after a block of at least 6
python3 bb6-1RB1RA_1LC1LD/py/blocks.py caseb 15 400 300 12 3000 # case B: offset 0 and two supply words, halting starts, the run
python3 bb6-1RB1RA_1LC1LD/py/blocks.py descents 8256 # the descents of the last block on the run to 10^12 steps (minutes)
python3 bb6-1RB1RA_1LC1LD/py/blocks.py residues 8256 18 27 54 81 162 # residues of the last two blocks on the run against the halting starts (minutes)
cd tools/py && python3 -m bbtools.invariants 1RB1RA_1LC1LD_1LD0LB_1RE0RF_---1RD_1RA1RB 12
cd tools/py && python3 -m bbtools.ctl 1RB1RA_1LC1LD_1LD0LB_1RE0RF_---1RD_1RA1RB 3