Busy Beaver Explorer / 1RB1RA_1RC1LB
What is known about 1RB1RA_1RC1LB, and what is open
1RB1RA_1RC1LB_1LD0RA_---0LE_1LC0LF_1RE0LB
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's structure is now proved in two layers. Lean has the machine as an explicit map on lists of block lengths, and a theorem that the machine halts exactly when that map's run reaches one specific shape. Read four macro steps at a time, that map is a carry wave running left through the blocks, and Lean now also proves that the halting shape is one arithmetic event: a single number built from the blocks being a power of two. What is open is whether it ever is.
The reduction walks through this link by link; level by level runs the machine in the browser at each level.
Status as of 5 November 2026.
In short
The question is open, and it is now a question about a list map. Lean proves that one macro step of the machine (a phase of transfers, then a sweep to the right or a carry to the left) is an explicit function next on the lists of block lengths, step counts included, and that the machine halts from blank tape iff the macro run reaches a halt. A macro step halts exactly when the head's block is odd and, after the transfers, every block to the left of the head is 2.
Running that map, Lean's kernel proves no halt in the first 2·1010 steps. Lean now also proves the exact machine-step count of each super step (below), so following the super orbit gives longer runs: no halt in the first 1.4·1016 steps checked by the kernel alone, and, with native_decide, no halt in the first 1024 steps by the plain orbit. Skipping over the cycles of the last 35 blocks, the kernel alone checks no halt in the first 4.4·1037 steps (below). In those runs the blocks reach the billions, far from all 2s. What is missing is an argument that the map never produces that shape.
The halting condition in one number, proved. Every fourth time A stands on the blank right of the tape, the tape is blocks p1, …, pm followed by 5, 0, and the next such tape follows from an explicit formula: with dm+1 = 20 and dl = pl + dl+1/2, a wave of halvings runs left while d is even and turns at the first odd d. Lean proves this super step from the macro map for every list, and proves that the machine halts from blank tape iff N = 10 + Σ pl·2m−l (the blocks read as binary digits) is a power of two at some super step of the orbit from (1, 6). The wave reaches the left end when 2m−1 divides N, which explains why the head gets there so rarely (computed, not part of the proof). Read from the right end, the super step is a cascade in which each block only passes something to the block on its left, so the last k blocks evolve on their own and fall into exact cycles (the last 44 repeat every 1.8·1021 super steps). A search that tabulates those cycles and skips over them finds no halt in the first 6·1023 super steps, 2.7·1049 machine steps (computed, not proved). Lean proves that the last blocks run on their own and that the tables are sound, and the same tables give no halt in the first 4.4·1037 steps, checked by the kernel alone in pieces (and, as a cross-check, in one native_decide evaluation).
Prior work
The machine is an open BB(6) holdout on @mxdys's lists (623 machines up to equivalence, 24 October 2026) and sits unannotated in the community ledger's "Cubic Mess" class. It is not a named cryptid and has no page on the bbchallenge wiki.
Google DeepMind's cryptids repository lists it as an open acceleration problem (PR #18, 27 October 2026), with a Lean proof that it halts iff a map on two stacks of block lengths halts. That map is the macro step here cut at other moments, and its higher-level map is exactly the event map of py/waves.py (each time A is on the blank right end), one level below the super step (py/deepmind.py checks it, lean/DeepMind.lean proves it for every event). Nothing found reduces it further; the super step's formula and the criterion on N appear to be new.
The machine 1RB1RA_1RC1LB_1LD0RA_1RA0LE_---0LF_0RD0LB, which the ledger says was merged into another equivalence class in April 2026, runs through the same tapes and halts from the same configurations (py/sibling.py), so these results should apply to it too. Its Collatz-like map is not Antihydra's or Hydra's: those iterate one integer under n → ⌊3n/2⌋, while here the state is a growing list and N does not determine the next N. Sources and details: notes/PRIOR_WORK.md.
What each result rests on
kernel Proved in Lean, kernel-checked
The machine halts iff N is ever a power of two
Let the super orbit start at P = (1, 6) (the tape [1, 6, 5, 0] at step 136) and go on by superstep. The machine halts from blank tape iff some P = (p1, …, pm) of the orbit has N = 10 + Σ pl·2m−l a power of two. Built on halts_iff: the proof follows the macro run, without step counts, from one super step to the next.
halts_iff_pow2' (the order of waves.py), halts_iff_pow2, run_halts_iff, lean/Wave.lean
The super step
From the tape [p1, …, pm, 5, 0] (A on the blank right of the last block), the macro run reaches [P′, 5, 0] with P′ = superstep P, or halts. With dm+1 = 20 and dl = pl + dl+1/2, the wave leaves d/2 at each block with d even; at the first odd di the block becomes (di + 5)/2 and the one to its left gains (di − 1)/2. At the left end it goes on halving, and halts when d reaches 1. Proved for every list and every block length, and every tape of the orbit is reached by the machine from blank tape (orbit_tape).
super_run, carry_wave, carry_left, orbit_tape, lean/Wave.lean
The single events, and DeepMind's high-level map
Each time A stands on the blank right of the tape (an event, four per super step), the next event follows in closed form. If the last two blocks are k and x and q = ⌊x/2⌋: for even x they become k + q + 1, q + 2; for odd x the wave of the super step starts at k with value k + q + 2, and the last block of the new tape is q. Proved from the macro map for every tape of the run's shape (the machine reaches the next event, or halts where the map says), and four events from [P, 5, 0] are the super step. So the machine halts iff the event orbit from [1, 2] (step 17) halts, and every tape of that orbit occurs. Google DeepMind's highLevelNext (cryptids, 27 October 2026), copied into core Lean, equals this map on every event, two steps later; their reduction is reached here again by another route.
ev_sound, carry_ev, ev4, halts_iff_ev, evOrbit_tape, lean/Events.lean; highLevelNext_eq, halts_iff_hl, lean/DeepMind.lean
The step count of a super step
From the tape [p1, …, pm, 5, 0] the machine reaches the next super-step tape in exactly superT steps, or halts right after that many: 200 steps to the first carry of the wave, then 2q2 + q − 5 for each block the wave passes with even d = 2q, then 2q2 + 4q + 17 + A where it turns at an odd d = 2q + 1, with A = 3 plus q + 1 for each block passed. At the left end the wave goes on with p = 0, and a halt there costs 11 steps. Proved for every list by following the timed macro steps of next_sound through the wave. It equals the sum of the four step counts of py/waves.py on 150,000 super steps (a test).
super_steps, carry_wave_t, superT, lean/WaveTime.lean
The step counts of single events
From each event (A on the blank right of the tape, four per super step) the machine reaches the next one in exactly evT steps, or halts right after that many. With the last block x and q = ⌊x/2⌋: 2q2 + 8q + 17 for even x; for odd x, 2q2 + 9q + 5 to start the wave, then 2q2 + q − 5 for each block it passes with even d = 2q and 2q2 + 4q + 11 + B where it turns at an odd d = 2q + 1, with B = q + 3 for the event's own q plus q + 1 for each block passed (a halt at the left end costs 11). Proved for every tape of the run's shape by following the timed macro steps through the wave with any right part; the four events of a super step add up to superT, and the timed event orbit from [1, 2] at step 17 is the machine's run step for step. Agrees with py/waves.py on the first 200,000 events.
ev_steps, carry_reachE, ev4_time, evOrbitT_tape, lean/EventTime.lean
When a super step halts
A super step halts iff N is a power of two. The wave passes a block exactly when d is even, so if it reaches the left end, 2m−1·d1 = N, and it halts there exactly when d1 is a power of two; if it turns at an odd di, N is an odd number of at least 3 times a power of two.
superL_none_iff, wave_none_iff, lean/Wave.lean
N only grows
N strictly increases at every super step that does not halt, so along the orbit from blank tape it is strictly increasing and meets each power of two at most once. Where the wave turns at block i (j = m − i) N gains more than 2j+1; at a return it is multiplied by more than (3 + s)/2. Since m is fixed between returns, the next return's d1 exceeds p1 + p2/2 + p3/4 + … for the blocks at any time before it.
superL_grows, orbit_grows, blank_orbit_grows (with leftEnd_grows, wave_grows), lean/Monotone.lean
The machine halts iff the macro run does
With X(ls, n, cs) = 0∞ 1lr 0 … 0 1l1 0 A> 1n 000 1c1 00 … 00 1cs 0∞, the run from blank tape is at X([1], 2, []) after 15 steps, and from every X the machine goes where the list function next says, in exactly the steps it says (next_sound). Every reachable X is well formed, so the machine halts from blank tape iff the macro run runM reaches a halt (halts_iff).
halts_iff, next_sound, runM_sound, lean/Macro.lean
When a macro step halts
A macro step from X(k :: ls, n, cs) halts iff n is odd and every block of (k + ⌊n/2⌋) :: ls equals 2: the carry to the left eats every block of 2 and reaches the left end.
next_halt_iff, lean/Macro.lean
Seven block rules
Transfer (two cells of the head's block move, one left, one right, 2n + 11 steps), the start and each block of the sweep to the right, and the four stages of the carry to the left; each for every block length and any surrounding tape.
transfer, empty_start, sweep_step, carry_start, carry_two, carry_exit, carry_one, lean/Rules.lean (generated by lean/rules.py)
No halt in 4.4·1037 steps
The tables of the last 1 to 35 blocks, built one level at a time from the blank-tape orbit with the plan of lean/CascadeRun.lean, then 6 passes of the last (8.8·1016 super steps each): 6.75·1017 super steps, to machine step 44,405,698,359,075,157,430,295,693,458,238,990,120, without a halt, the same bound as the native_decide run. One evaluation of the tables by the kernel runs out of memory past about 18 levels, so the tables are written out (by lean/cycle_gen.py, not trusted) and checked in 33,760 pieces of 3,000 entries, each a separate decide +kernel; Lean chains them (step_sound). About 21 CPU hours, six hours on four cores (30 levels and 4 passes, 1.2·1032 steps, take 5,920 pieces and 4 CPU hours). By the plain orbit, the kernel also checks the first 107 super steps in 1,000 chunks between checkpoints from c/orbitck.c (not trusted: every chunk is recomputed), 14,027,148,336,216,160 machine steps (about 50 minutes on three cores). The macro map, evaluated directly, gives 2·1010 steps (105 macro steps), and step by step the kernel checks 20,000.
blank_runs_cycles, lean/CycleRun.lean, lean/CycleCert.lean (pieces generated by lean/cycle_gen.py, checked by lean/check_cycles.sh 35 6); blank_runs_1_4e16, lean/OrbitKernel.lean, lean/Orbit/K*.lean (generated by lean/orbit_gen.py, checked by lean/check_orbit.sh); blank_runs_2e10, lean/MacroRun.lean; blank_runs_20000, lean/Blank.lean
Two shift rules
State A runs right over a block of n ones in n steps; state B runs left over a block of n ones to the 0 before it in n + 1 steps; for every n and any surrounding tape.
a_sweep, b_sweep, lean/Rules.lean
The last blocks run on their own; the skip tables are sound
Split the list (nearest first) as B ++ U: the super step of B ++ U is B's own step followed by what B passes on (nothing, an add, or a wave) applied to U, and its step count superT splits the same way. A table that is one period of B can stand in for B: running U on it follows the timed orbit over whole periods. A table for one more level, built over L passes, is a period as soon as the level comes back to its block, which the builder checks. Every list, every k.
superL_split, superT_split, pass_sound, build_rep, drive_sound, runs_of_drive, lean/Cascade.lean
Each level cycles, or the machine never halts
From any state, the last k blocks on their own either come back to themselves after some point (and then have a table of one period) or never again pass anything to the left. The proof is by induction on k: a level fed by a cycle that sends it a wave each period stays below a bound (a wave halves it), so it repeats; fed by one that sends no wave, it passes nothing on. A silent bottom on the orbit from blank tape means the wave never reaches the left end again, so the machine never halts. So once the orbit has k blocks, either it halts soon after, or the last k blocks cycle, or it never halts. Which case holds is not decided. On the orbit, the last 1 to 35 blocks are checked to cycle, each with its least period (4, 8, 32, 128, 256, 1,024, …, 8.8·1016 super steps for the last 35): the table of each level is written out and checked in pieces, the next block comes back after L passes of it and not before, and then L times the least period below is the least period (least_append). The last six are also checked by decide directly.
cycles_or_silent, rep_of_cycles, never_halts_of_silent, cycles_or_never_halts, cycle₁–cycle₆, lean/Cycles.lean; cycle1–cycle35, lean/CycleRun.lean
The period factors are 1, 2, 4 or 5
Each block added to the cycling bottom multiplies its period by a factor L. Mod 5 a wave acts on a block as p → 3(p + h), whether the wave turns there or passes ((d + 5)/2 and d/2 are both 3d mod 5), and an add as p → p + v. So over a period the next block moves mod 5 by r → 3Wr + b, W the waves it receives per period. Lean proves that the blocks of a cycle are distinct mod 5, so L is the period of the residue under that affine map: L is 1, 2, 4 or 5, never 3; 1 or 4 if W is odd, 1 or 2 if W ≡ 2 mod 4, and if W ≡ 0 mod 4, 5 when b ≠ 0 and 1 when b = 0. This is why every period is 2a·5b.
cycle_residues, period_factor, level_period, rule₁–rule₃, lean/Periods.lean
The low bits of N, and the two residues it never takes
N mod 2k is a function of the last k blocks, so on the orbit it follows their cycle. From super step 7 on, N ≡ 2 mod 4 exactly at one super step in eight (the last two blocks at [12, 26]; a uniform law would give one in four). Three super steps after [12, 26], N is larger by exactly 106, whatever the other blocks. And from some super step on, N is never 3030 or 4054 mod 212: the cycle of the last 12 blocks (327,680 super steps) is checked in 20 pieces. Both are the 2-adic class of −42, which is thin on this orbit's cycles but not on others of the same map; it says nothing about powers of two.
bigN_bottom, mod4_blank, plus106, neg42_iff, never_bad, lean/Residues.lean; never_3030_4054, lean/ResidueRun.lean (in check_cycles.sh from 12 levels)
native Proved in Lean with native_decide
No halt in 4.4·1037 steps, in one evaluation
The tables for the last 1 to 35 blocks, each built and checked inside the evaluation, and then 6 passes of the last (8.8·1016 super steps each): 6.75·1017 super steps, to machine step 44,405,698,359,075,157,430,295,693,458,238,990,120, without a halt. About 4 minutes; the plan (py/superrun.py plan 35 6) is only a hint. The kernel now checks the same bound in pieces (above), so this run is a cross-check.
blank_runs_4e37, lean/CascadeRun.lean
No halt in 1024 steps
The super orbit continued to 9.9·1010 super steps by compiled evaluation (native_decide), in 99 chunks after the kernel's 107: more than 1024 machine steps (1,020,655,748,109,356,278,914,592) without a halt. This covers the earlier C run of the wave model to 3.7·1022 steps. With the macro map directly: 9·1013 steps (107 macro steps); step by step: 10,000,000.
blank_runs_1e24, lean/OrbitNative.lean, lean/Orbit/N*.lean (check_orbit.sh all, about 1.7 hours on four cores); blank_runs_9e13, lean/MacroRun.lean; blank_runs_10M, lean/Blank.lean
trusted Computed, not proved
The Python macro model
py/macro.py computes the same map; it is tested against the reference simulator at every macro configuration of the first 1,000 macro steps (1,322,171 machine steps, the same count Lean's runM_1000 gives) and on built configurations that halt.
py/macro.py, tests/test_machine.py
No simple conserved quantity
No quantity a·(number of 1s) + b·(head position) + W[state] is conserved modulo any m from 2 to 12. (The other machine has one modulo 3, which the same search finds.)
tools/py/bbtools/invariants.py
The next return to the left end
After step 2,047,931 the head next reaches new tape on the left at step 26,618,972,322, as the wave model predicted; a direct run to 2.7·1010 steps confirms it and finds no other new left cell in between.
tests/test_waves.py (WAVES_LONG=1)
No halt in 2.7·1049 steps
The super orbit runs 599,258,349,609,526,266,612,571 super steps (6·1023), to machine step 27,264,770,338,578,141,293,580,742,812,737,757,101,373,338,361,002, without N becoming a power of two. The wave reaches the left end 38 times on the way (23 of them beyond the old bound of 3.7·1022); N comes closest at super step 7·1021, 0.5% above 2149. That the orbit decides halting is proved; the run is C (checked against blkrun.c, a direct run, an independent Python version and waves.py), and the step count is a per-level split of the super step's step count.
c/superrun.c, py/superrun.py, tests/test_superrun.py, runs/superrun_long.txt
The last blocks are periodic
Numbering the blocks from the right, block k only receives an add or a wave from block k−1 and passes one on, so the last k blocks are a closed system. Each wave halves a block, and they fall into exact cycles: the last block 11 → 13 → 14 → 12, the last two with period 8, the last 20 with period 1.7·1010, the last 44 with period 1.8·1021 super steps (each a 2a·5b). The search checks each cycle before using it. That every level either cycles or goes silent is now proved in Lean (above), and so is the rule for the factors; the periods of the last 1 to 35 blocks are kernel-checked (above), and beyond those they are computed. Every one of the 44 factors is the one the mod-5 rule predicts, and from the fourth block on a settled block remembers only its residue mod 5 from one period to the next.
c/superrun.c (lines table of runs/superrun_long.txt; -r and runs/periods_rules.txt for the rule), notes/LAB_NOTES.md
The next return needs 280 | d1
At the end of the long run (super step 6·1023) the top four blocks give p1 + p2/2 + p3/4 + p4/8 = 1.18·1024 = 279.96, so by orbit_grows the next return halts only if d1 = 2a with a ≥ 80.
py/top_stats.py odds; the blocks from c/superrun.c (runs/superrun_long.txt)
The law of N mod 2k at the right end
N mod 2k depends only on the last k blocks, which cycle; over one exact period of the last 18 (1,048,576,000 super steps) v2(N) = j occurs 1, 0.5, 1.25, 1.75, 2.13, 1.44, … times 2−(j+1), then near 1.28; the next bit given the lower ones is off from a fair coin by 0.07 on average at bit 4 and 0.0018 at bit 17, so the 2-adic law of N has a density (no class above 3.5 times uniform); and N is never 3030 or 4054 mod 212 (now proved, above), the only residues mod 218 it misses.
c/bottom2adic.c, runs/bottom2adic_18.txt, tests/test_top.py
heuristic Evidence only
Far from the halting shape
In 107 macro steps the left list of blocks holds blocks in the hundreds of thousands; halting needs every block to the left of the head to be 2.
notes/LAB_NOTES.md
Why the returns to the left end are rare
The wave is a binary carry: reaching the left end needs v2(N) ≥ m − 1, about once in 2m−1 super steps if N's low bits behave like coin flips, and each return adds blocks. They do not quite: from the periodic tables, a wave passes the last k blocks at the rate 1.2764·2−k per super step (computed, converged to four digits by k = 40), so the low bits of N lean towards 0 by a constant factor. The observed gaps are somewhat shorter still. The returns do not stop; they thin out.
notes/LAB_NOTES.md
Almost certainly no halt
At a return the deciding number d1 is now about 1.9·1024 (81 bits) and has grown by about 2.1 bits per return; if it behaved like a random integer, the chance of ever hitting a power of two from here would be about 5·10−25 (10% to 90% over resampled futures: 5·10−26 to 1.4·10−24). Earlier versions said 1.9·1027 and 10−27, from a miscounted d1. The rule for the periods explains the last blocks completely but gives no obstruction: halting is decided at the top, where the blocks are young. N shows no modular obstruction (see below).
py/top_stats.py odds, runs/odds.txt, pages/1RB1RA_1RC1LB/top-blocks.html
The random model holds on the map within a factor of about 2, and valuations are geometric
From 60,000 random starts (522,749 returns, d1 up to 230) the super step halts 2,018 times against 2,023.7 predicted by 1/(d1 ln 2). Near-halts (odd part of d1 below 2c, c ≤ 20) come at 0.4 to 1.4 times the predicted rate at every scale; v2(d1) is geometric: the shortfall beyond 7 seen in that run (about 15%, 3σ) is an artefact of its starts, which repeat and merge (2 blocks of 1 to 100 have only 104 tapes). Over 107 starts (c/ensemble_fast.c) the old design shows it again (0.90 of the geometric rate at t = 8), but with each return counted once (74 of its 87 million returns repeat an earlier one) it is 1.00 ± 0.01 at t = 8 and within 4% to t = 12; from 107 starts of 2 to 8 blocks up to 106, P(v2 ≥ t)·2t is 1.000 ± 0.002 at t = 8 and within 1% of 1 to t = 12 and within its errors beyond, with 92 halts against 91 expected; orbits of 1014 super steps (d1 past 240) agree. d1's residues and leading bits are within a few percent of uniform. On the blank-tape orbit, waves pass each of the top 24 blocks half the time (0.4998 to 0.5006 where over 105 waves reach them).
c/ensemble.c, c/ensemble_fast.c, py/top_stats.py, runs/ensemble_summary.txt, runs/valuation_test.txt, runs/toppass_1e17.txt; pages/1RB1RA_1RC1LB/top-blocks.html
No invariant keeps N off the powers of two
Searched for a property of the orbit that every power of two lacks; none found. For every odd q ≤ 127, N takes every residue a power of two takes mod q, also jointly with N's bit length (2a has a + 1 bits). N's popcount and leading bits look like a random number's (it comes within 15 zeros of a power of two). Lower bounds on the blocks cannot help, since halting depends only on the sum N. And the super step started from 3,600 small tapes halts 217 times against about 239 expected if the deciding number were random: the map has no invariant of its own that forbids halting. The one exact pattern found, a four-step cycle 11 → 13 → 14 → 12 of the last block (proved by hand from the super-step formula), only fixes N's parity pattern.
py/n_search.py, notes/LAB_NOTES.md
open Open
Whether it halts
Whether N = 10 + Σ pl·2m−l is ever a power of two along the super orbit from (1, 6). By the proved halts_iff_pow2' this is exactly the question whether the machine halts: a Collatz-like question about one orbit.
Check it yourself
bash scripts/setup-lean.sh # Lean 4.34.0, core only
. /etc/profile.d/lean.sh
bb6-1RB1RA_1RC1LB/lean/check.sh # the library, then Machine, Rules, Blank, Macro, MacroRun, Wave, Events, DeepMind, Monotone, WaveTime, EventTime, Cascade, CascadeRun, Cycles, Periods (about 6 min)
bb6-1RB1RA_1RC1LB/lean/check_orbit.sh all # the long runs in parallel (about 3 CPU hours kernel, 6 native)
bb6-1RB1RA_1RC1LB/lean/check_cycles.sh 35 6 # the tables of 35 levels in pieces, kernel only (about 21 CPU hours)
python3 tools/tests/test_tools.py # the shared tools
python3 bb6-1RB1RA_1RC1LB/tests/test_machine.py
python3 bb6-1RB1RA_1RC1LB/py/macro.py 50 # the macro run
python3 bb6-1RB1RA_1RC1LB/tests/test_waves.py # the wave model against direct simulation (about 25 s)
python3 bb6-1RB1RA_1RC1LB/tests/test_superrun.py # the tabulated search against blkrun, waves.py and Python (about 20 s)
python3 bb6-1RB1RA_1RC1LB/py/n_search.py residues 4000000 # the invariant search (also: digits, starts)
python3 bb6-1RB1RA_1RC1LB/tests/test_top.py # the ensemble and 2-adic tools against waves.py (seconds)
python3 bb6-1RB1RA_1RC1LB/py/top_stats.py odds # the next return's floor and the odds of a halt