Busy Beaver Explorer / 1RB1RA_1RC1LB / the reduction

How 1RB1RA_1RC1LB comes down to one number

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 follows its run from single steps down to a question about one number, link by link, and says for each link what it rests on: a proof checked by Lean, a program in the repository that has been tested but not proved, or only evidence.

The interactive level-by-level explainer runs each level in the browser. The proof status page lists every result about the machine, and the top blocks looks at where halting is decided and how far the heuristic of §7 can be trusted.

As of 30 October 2026. The reduction is from pull requests #116 (the macro step, proved), #117 (the wave and the number N, computed), #119 (the super step and the N criterion, proved) and #118 (a search for an invariant, none found); the cycles of the last blocks (§6) from #126.

In short

Proved in Lean (kernel only): the machine is an explicit map next on lists of block lengths, step counts included, and it halts from blank tape iff that map's run reaches one shape: the head's block is odd and, after its transfers, every block to the left of the head is 2. Read every fourth time the head stands on the blank right end of the tape, the run is a super step on a list P = (p1, …, pm), and with N = 10 + Σ pl·2m−l, the machine halts from blank tape iff N is ever a power of two along the super orbit from P = (1, 6) (halts_iff_pow2').

Proved, kernel only: information in the super step only flows left, so the last k blocks run on their own, and for every k they eventually cycle or go silent, and silent means the machine never halts. The last 1 to 35 blocks are checked to cycle, with their least periods (§6).

Computed, not proved: the long runs: the last 44 blocks of the list fall into exact cycles, and a search that skips over them finds no halt in the first 2.7·1049 steps.

Open: whether N is ever a power of two. A search for an invariant that rules it out found none; nothing suggests it will be: no halt in the first 4.4·1037 steps (kernel, by tables of the last blocks) or 2.7·1049 (computed), and a heuristic puts the chance of a halt from here on at about 10−27. But no proof rules it out.

The chain of reductions

kernel checked by Lean's kernel alone native Lean with compiled evaluation computed C or Python in the repository, tested, not proved on paper a short proof on this page heuristic evidence only open not known
  1. 0
    The machine. Six states, one halting transition (D reading 0). the definition, lean/Machine.lean
  2. 1
    Seven block rules. From step 15 on, the tape is blocks of ones, and the head moves cells between blocks by seven moves, each for every block length. kernel §1, lean/Rules.lean
  3. 2
    The macro step. The machine goes from every configuration X(ls, n, cs) to the one the list function next gives, in the number of steps it gives. kernel §2, next_sound
  4. 3
    The halting shape. The machine halts from blank tape iff the macro run halts, and a macro step halts iff n is odd and every left block, after the transfers, is 2. kernel §3, halts_iff, next_halt_iff
  5. 4
    The halving wave. Cut at the moments A stands right of the last block, a run of macro steps is one wave of halvings running left; every fourth such moment the tape is [P, 5, 0] and the next P follows by the super step. kernel for the super step and the single events; computed for the step counts of single events. §4, super_run in lean/Wave.lean, ev_sound in lean/Events.lean; py/waves.py, tests/test_waves.py
  6. 5
    The number N. The wave goes v2(N) + 1 blocks deep, reaches the left end iff 2m−1 divides N, and the machine halts iff N is a power of two. kernel §5, superL_none_iff, halts_iff_pow2'
  7. ↻
    The last blocks cycle. Information only flows left, so the last k blocks run on their own; each level cycles or goes silent, and silent means no halt. kernel for that and the last 35 levels; computed up to 44. §6, lean/Cycles.lean, py/cycles.py
  8. ?
    Is N ever a power of two? open heuristic almost certainly not. No invariant found. N only grows (kernel). §7, the top blocks, py/n_search.py

1. The tape is blocks, moved by seven rules kernel

Write tapes left to right, S> for the head in state S on the next cell, 1^n for n ones, and L, R, Q for any tape. The symbolic prover (tools/py/bbtools/symtm.py) proves each rule below in Lean from the machine's table, for every block length and any surrounding tape; lean/rules.py lists them and generates lean/Rules.lean.

rulefromtostepswhat it does
transferL 0 A> 1^(n+2) 000 RL 1 0 A> 1^n 000 1 R2n + 11two cells of the head's block move out, one to the block on the left and one past the 000
empty_startL 0 A> 000 RL 1 0 A> 1 1 R15the block is used up: the left block gains one and A starts a sweep right
sweep_stepL A> 1^m 00 1 RL 1^(m+2) 0 A> Rm + 3one block of the sweep: 00 becomes 0 and the block gains two
carry_startL 0 A> 1 000 RL 0 F> 1 001 R6one cell is left: F starts carrying left
carry_twoL 0 1^(j+2) 0 F> 1 QL 0 1^j F> 1 001 Q5F takes two cells of the block on its left and leaves 001 on the right; a block of exactly 2 disappears
carry_exitL 0 1^(m+1) F> 1 QL 1 0 A> 1^m 0 Qm + 4the carry stops inside a block, which starts a new transfer phase
carry_oneL 0 1 0 F> 1 QL 1 0 A> 1 1 Q15the carry meets a block of one cell; A sweeps right

Two shift rules underlie them: A runs right over a block of n ones in n steps (a_sweep), and B runs left over one to the 0 before it in n + 1 steps (b_sweep).

2. The macro step: a map on lists kernel

A macro configuration is

X(ls, n, cs) = 0^∞ 1^l_r 0 … 0 1^l_1 0 A> 1^n 000 1^c_1 00 1^c_2 … 00 1^c_s 0^∞

with ls = [l_1, …, l_r] the blocks left of the head, nearest first, separated by single 0s; n the block under the head; and cs the blocks to the right, separated by 00 (and by 000 from the head's block). The run from blank tape is at X([1], 2, []) after 15 steps (init_X). Write bump for "the first block gains one, or a new block 1 if there is none". One macro step, next ls n cs, is:

  1. Transfers. q = ⌊n/2⌋ transfers: l_1 and c_1 each gain q, the head's block drops to n mod 2; q(2(n mod 2) + 2q + 9) steps.
  2. n even: sweep right. l_1 gains one and A sweeps right to the end of the tape. Every 00 becomes 0: c_1 gains 4 (two from empty_start, two from its sweep_step) and c_2 … c_(s−1) gain 1 (A takes one cell of each to cross into it, and the sweep adds two); all of them join the left list, and the last block becomes the head's block (c_s − 1, or c_1 + 2 if there is only one). With cs empty the result is X(bump ls, 2, []).
  3. n odd: carry left. F carries left. Every block equal to 2 it meets disappears and leaves a 001 on the right (5 steps each). At the first block k ≠ 2, after i twos:
    • k ≥ 3: X(bump(rest), k − 3, [1]^(i+1) ++ bump(cs)), a new transfer phase in the middle of the tape;
    • k = 1: bump(rest), then a sweep right as in 2, over [1]^i ++ bump(cs), starting from a block of 2;
    • no such block, because every block to the left is 2: the machine halts, 6 steps later (F B C D E C, then D reads 0).

next_sound says that from X ls n cs the machine reaches exactly the configuration next gives, in exactly the steps it gives, or halts where it says. It is proved for every case and every block length, by Lean's kernel alone. py/macro.py computes the same map in Python (tested against direct simulation at every configuration of the first 1,000 macro steps, 1,322,171 machine steps, the same count as Lean's runM_1000).

3. Halting iff the macro run halts kernel

Every reachable macro configuration has a left block and no empty blocks (Good, next_fine), so next never gets stuck and every macro step takes at least one machine step. Together with next_sound that gives

halts_iff: the machine halts from blank tape iff the macro run runM reaches a halt.
next_halt_iff: a macro step from X(k :: ls, n, cs) halts iff n is odd and every block of (k + ⌊n/2⌋) :: ls equals 2.

So the question is entirely about the orbit of an explicit list map. For example X([2, 2, 2], 1, cs) and X([1], 3, cs) halt. Running the map, Lean's kernel proves no halt in the first 2·1010 steps (105 macro steps, blank_runs_2e10), and with native_decide none in the first 9·1013 (107 macro steps, blank_runs_9e13). In those runs the left list holds blocks in the hundreds of thousands, nowhere near all 2s.

4. The halving wave and the super step kernel computed

The same run, cut at different moments. Call it an event when A stands on the blank just right of the last block. The tape is then 1^b_1 0 1^b_2 0 … 0 1^b_n A>0, blocks separated by single 0s (the last block may be empty), and the next event follows from b alone.

Between two events a wave runs left from the right end. At each block it carries a value c, at first the last block less one. It halves the block with ⌊c/2⌋ cycles (1^y 0 [B] 1^m 000 1^k → 1^(y+1) 0 [B] 1^(m−2) 000 1^(k+1), 2m + 5 steps each). If c is odd the wave turns and A sweeps back to the right end. If c is even, it moves on to the next block left, of length y, with c' = y + c/2 − 2. At the left end y = 0: the wave keeps halving into new tape (c → c/2 − 2), and if it reaches c = 0 the next transitions are B0 C0 D1 E0 C0 D0, the halt. So a wave that reaches the left end halts the machine iff it arrives with c + 4 a power of two.

In the terms of §2 a wave is a run of macro steps: its cycles are transfers, "c even, move on" is a carry (n odd), a level with a block of 2 is a block the carry eats, the turn is a sweep (n even), and the halt at the left end is the carry eating blocks of 2 all the way to the left end. py/waves.py lists all the local rules with their step counts.

The super step. From the fourth event on (step 136, tape [1, 6, 5, 0]), every fourth event has the tape [p_1, …, p_m, 5, 0], and the next such event depends on P = (p_1, …, p_m) only. Put d_(m+1) = 20 and d_l = p_l + d_(l+1)/2 for l = m, …, 1, stopping at the first odd one. If i ≥ 2 is the largest index with d_i odd, the wave turns there and

P' = (p_1, …, p_(i−2),  p_(i−1) + (d_i − 1)/2,  (d_i + 5)/2,  d_(i+1)/2, …, d_m/2).

If d_2, …, d_m are all even, the wave reaches the left end. Write d_1 = 2^s·u with u odd. If u ≥ 3 the tape grows on the left, P' = ((u−1)/2, (u+5)/2, u, 2u, …, 2^(s−1)·u, d_2/2, …, d_m/2) (with u = 3 the head reaches the left end in state F, as at steps 81 and 1,135). If u = 1 the machine halts.

What this rests on. The wave's rules were found by hand and are checked by tests/test_waves.py: every event of the first 109 steps (12,927 events) against direct simulation with exact step counts; every new left cell up to 1010 steps; a direct run to 2.7·1010 steps that confirms the predicted return to the left end at step 26,618,972,322; and from each of the first 2,000 configurations of py/macro.py, the cut that Lean proves, direct simulation reaches the next event that waves.py gives. The super step is checked against four wave steps for 150,000 super steps. c/blkrun.c is the same model in C with 128-bit step counts.

What Lean proves. super_run (lean/Wave.lean, kernel only) proves the super step from the macro map of §2: from the tape [p_1, …, p_m, 5, 0], which is the macro configuration X(5 :: [p_m, …, p_1], 0, []), the macro run reaches [P', 5, 0] with P' = superstep P, or halts, for every list. orbit_tape says every tape of the super orbit from (1, 6) occurs on the run from blank tape. Lean follows this run without step counts; the step counts are proved separately, for the super step (super_steps, lean/WaveTime.lean) and for each single event (ev_steps, lean/EventTime.lean), and they are the formulas of waves.py.

The single events in Lean. ev_sound (lean/Events.lean, kernel only) proves the events themselves. If the tape ends in blocks k, x and q = ⌊x/2⌋: for even x the next event ends in k + q + 1, q + 2; for odd x the wave above starts at k with value k + q + 2 (in the d of the super step) and the next event ends in the blocks it leaves, then q. The machine reaches that event, or halts where the map says, for every tape of the run's shape. Four events from [P, 5, 0] are the super step (ev4), so the machine halts iff the event orbit from [1, 2] (step 17) halts (halts_iff_ev). This event map is Google DeepMind's high-level map (prior work): lean/DeepMind.lean copies their highLevelNext into core Lean and proves it equal to the event map on every event (highLevelNext_eq). ev_steps (lean/EventTime.lean, kernel only) adds the step count of each event: 2q² + 8q + 17 for even x, and for odd x 2q² + 9q + 5 plus the time of the wave, priced as in the super step; the four events of a super step add up to superT (ev4_time).

5. Halting iff N is a power of two kernel

Read the blocks as binary digits, p_m the units, and add 10:

N = 10 + Σl=1…m pl·2m−l. Given the super step of §4: the wave goes v2(N) + 1 blocks deep, it reaches the left end iff 2m−1 divides N, and the machine halts iff N is a power of two.

Proof. Write N_l = 10 + Σk≥l p_k·2^(m−k), the part of N from block l on, so N = N_1.

(a) If d_(l+1), …, d_m are all even, then d_l·2^(m−l) = N_l. For l = m: d_m = p_m + 20/2 = N_m. Going left, d_(l+1) is even, so d_l·2^(m−l) = p_l·2^(m−l) + d_(l+1)·2^(m−l−1) = p_l·2^(m−l) + N_(l+1) = N_l.

(b) Depth. Let i ≥ 2 be the largest index with d_i odd. By (a), N_i = d_i·2^(m−i) has exactly m − i factors of 2, and N − N_i = Σk<i p_k·2^(m−k) is divisible by 2^(m−i+1). So v_2(N) = m − i: the wave turns at block i = m − v_2(N) and goes m − i + 1 = v_2(N) + 1 blocks deep.

(c) The left end. If no such i exists, (a) applies at l = 1 and N = d_1·2^(m−1), so 2^(m−1) divides N. If one exists, v_2(N) = m − i ≤ m − 2 and it does not.

(d) Halting. The machine halts in this super step iff the wave reaches the left end and u = 1, that is, iff d_1 = N / 2^(m−1) is a power of two, so N is a power of two. Conversely, if N is a power of two then N > p_1·2^(m−1) ≥ 2^(m−1), so 2^(m−1) divides N, the wave reaches the left end by (c), and d_1 = N / 2^(m−1) is a power of two. ∎

Lean checks the same statement: superL_none_iff (a super step halts iff N is a power of two) and, composed with §3 and super_run, halts_iff_pow2': the machine halts from blank tape iff some P of the super orbit from (1, 6) has N a power of two. Both are kernel-checked with the standard axioms only. The argument above is the hand version.

6. Why the last blocks cycle kernel computed

The head sweeps back and forth, but information in the super step only flows one way: leftward. Read §4 one block at a time, numbering the blocks from the right (level 1 is p_m, the last block). A wave starts at the right end with the same value every super step, h = 10 (that is, d_(m+1)/2). At a block with value p, let d = p + h:

  • if d is even, the block becomes d/2 and the wave goes on left with h = d/2;
  • if d is odd, the block becomes (d + 5)/2, the block on its left gains (d − 1)/2, and the super step ends.

Nothing is ever passed to the right. So a block's next value depends only on its own value and on what arrives from its right, and the last k blocks are a closed system: they evolve by a map of their own (bstep), and all they do to the rest of the tape is send one wave or one add to the left, or nothing. Lean proves this split for every list (superL_split, with the step counts superT_split, lean/Cascade.lean). What keeps changing is the left part of the tape; its changes just never travel back.

The induction from the right.

  1. The last block gets the same input every super step. From p it goes to (p + 10)/2 or (p + 15)/2, so it soon stays below 16, and a deterministic system with finitely many states repeats: 12 → 11 → 13 → 14 → 12.
  2. The next block gets a periodic input, the output of that cycle. The adds push it up by a bounded amount per period, and each wave roughly halves it (a wave h takes q to at most (q + h + 5)/2). So it stays bounded, and once the last block cycles the pair is again a finite deterministic system. It repeats too, with period 8.
  3. Each further level works the same way: if the levels below cycle with period m and send at least one wave per period, the next block, read once per period, goes from q to F(q) with 2F(q) ≤ q + 2W (W bounds what one period adds), so it stays below q_0 + 2W and repeats by pigeonhole. The new period is m times a whole number.

There is one way this can fail: a cycle that sends no wave to the left, only adds. The next level then only grows, never cycles, and never sends anything further. But then the wave never reaches the left end again, so the machine never halts.

cycles_or_silent: for every k and every state of the last k blocks, after some number of super steps the last k blocks on their own either cycle or are silent (never send anything left again). A cycling bottom has a table of one period (rep_of_cycles).
never_halts_of_silent: a silent bottom on the orbit from blank tape, with blocks to its left, means the machine never halts.
cycles_or_never_halts: so once the orbit has k blocks, either the machine halts soon after, or the last k blocks cycle, or the machine never halts. All three kernel-checked (lean/Cycles.lean).

The bottom levels, one by one. On the orbit from (1, 6), every level so far cycles. The period and the super step it starts at are checked by Lean's kernel for the last 1 to 6 blocks (cycle₁ to cycle₆, by decide; each period comes back and half of it does not, so it is the least one). The least periods of the last 1 to 35 blocks are kernel-checked too, by tables (below). The other columns are computed, by py/cycles.py, and agree with the tables of c/superrun.c (tests/test_superrun.py).

last blocksleast period (super steps)periodic from super steptop block's valueswaves / adds sent left per periodmachine steps per period in these blocks
14 kernel3 kernel11–14, cycling 12 → 11 → 13 → 142 / 21,920
28 kernel7 kernel19–42, cycling 26, 21, 31, 42, 27, 19, 29, 403 / 18,285
332 kernel11 kernel27–48 (13 values)7 / 557,413
4128 kernel31 kernel37–152 (37 values)14 / 14413,014
5256 kernel60 kernel70–380 (48 values)11 / 171,624,541
61,024 kernel163 kernel162–1,042 (98 values)21 / 2314,553,949

Values, waves, adds and steps computed. The machine steps count 210 per super step, the wave's cost at each of these levels that it reaches, and 17 for each add received among them (the convention of c/superrun.c).

Further up kernel to 35 blocks, computed to 44. Each further level multiplies the period by 1, 2, 4 or 5. From the 7th to the 44th last block the factors are ×4, ×1, ×4, ×4, ×5, ×1, ×4, ×4, ×2, ×5, ×4, ×5, ×4, ×4, ×4, ×4, ×5, ×1, ×1, ×4, ×4, ×4, ×2, ×1, ×2, ×4, ×4, ×4, ×4, ×4, ×4, ×2, ×4, ×1, ×2, ×4, ×5, ×4, so the last 44 blocks repeat every 1.8·1021 super steps (c/superrun.c, runs/superrun_long.txt, which checks each cycle before using it). Lean's kernel checks the first 24 of these factors, so the least periods of the last 1 to 30 blocks, up to 1.7·1014 super steps (cycle1 to cycle30, lean/CycleRun.lean). It builds the table of each level from the one below as lean/CascadeRun.lean does, but one evaluation of all of them runs out of memory past about 18 levels, so the tables are written out by a program and checked in 5,920 pieces of 3,000 entries, each by decide +kernel (lean/CycleCert.lean); nothing written is trusted. A level's block comes back after L passes of the table below and not before, so L times the least period below is the least period (least_append). Of the 43 factors after the first, 25 are 4, 7 are 2, 6 are 1 and 5 are 5. Every level so far sends waves on, so the silent case has not occurred.

Why the factors are 1, 2, 4 or 5 kernel. A wave takes a block to (d + 5)/2 or d/2, and modulo 5 both are 3d, because 2·3 = 6 ≡ 1 and the 5 vanishes. So modulo 5 a wave acts on a block as p → 3(p + h) whichever way it goes, and an add as p → p + v. Over one period of the levels below, the next block therefore moves modulo 5 by an affine map r → 3^W·r + b, where W is the number of waves it receives per period. Lean proves that the blocks of a cycle are all different modulo 5, so the factor is the period of the block's residue under that map, and an affine map of the five residues only has cycles of length 1, 2, 4 and 5:

  • W odd (3W is 3 or 2, of order 4): the factor is 4, or 1 if the residue is the map's fixed point;
  • W ≡ 2 mod 4 (3W ≡ −1): 2, or 1 at the fixed point;
  • W ≡ 0 mod 4 (3W ≡ 1, a pure shift): 5 if the shift b is not 0, and 1 if it is.

That is why every period is 2a·5b and a factor of 3 never occurs (cycle_residues, period_factor, lean/Periods.lean). computed All 44 factors of the run are the ones the rule predicts (c/superrun.c -r, runs/periods_rules.txt). From the fourth level on, a settled block keeps nothing of its value but its residue modulo 5: the pass map sends any block near the cycle to the same place as any other with the same residue. So the whole state of the settled levels is one residue modulo 5 per level.

What this gives, and what it does not. The cycles are what make the long searches fast: c/superrun.c and lean/CascadeRun.lean replace the bottom levels by a table of one period and skip over it. They say nothing about the left end, where the wave arrives with d_1 and N's fate is decided: the list keeps growing there, each new level brings a longer period, and the orbit as a whole never repeats. Lean does not decide which of the three cases of cycles_or_never_halts holds, and even cycles at every level would not by themselves rule out a halt. The interactive explainer, level 5, finds these cycles in the browser.

What is proved, what is trusted, what is heuristic

claimstatusrests on
The seven block rules and the two shift rules, for every block lengthkernellean/Rules.lean, generated by lean/rules.py
The machine does what next says, step counts includedkernelnext_sound, lean/Macro.lean
Halts from blank tape iff the macro run halts; when a macro step haltskernelhalts_iff, next_halt_iff
The super step, for every list; every tape of its orbit is on the runkernelsuper_run, orbit_tape, lean/Wave.lean
Halts iff N is ever a power of two along the super orbit from (1, 6)kernelsuperL_none_iff, halts_iff_pow2'; the hand proof in §5
N strictly increases at every super step, so the orbit meets each power of two at most oncekernelsuperL_grows, orbit_grows, lean/Monotone.lean; the top blocks, §2
No halt in the first 2·1010 stepskernelblank_runs_2e10, lean/MacroRun.lean
No halt in the first 4.4·1037 steps (6.75·1017 super steps), by the tables of the last 1 to 35 blockskernelblank_runs_cycles, lean/CycleRun.lean, checked in pieces by lean/check_cycles.sh 35 6
No halt in the first 9·1013 stepsnativeblank_runs_9e13, also trusts Lean's compiler
py/macro.py computes nextcomputedtested against direct simulation for 1,000 macro steps
The single events, four of them the super step; DeepMind's highLevelNext is this event mapkernelev_sound, ev4, halts_iff_ev, lean/Events.lean; highLevelNext_eq, lean/DeepMind.lean; §4
The step counts of single eventskernelev_steps, ev4_time, lean/EventTime.lean; also py/waves.py, tests/test_waves.py
The last k blocks run on their own, step counts included; a table built for one more level is checked to be a periodkernelsuperL_split, superT_split, build_rep, lean/Cascade.lean
The same 4.4·1037 steps by those tables in one evaluation (a cross-check)nativeblank_runs_4e37, lean/CascadeRun.lean
For every k, the last k blocks eventually cycle or go silent, and a silent bottom means no haltkernelcycles_or_silent, never_halts_of_silent, cycles_or_never_halts, lean/Cycles.lean; §6
The last 1 to 6 blocks cycle on the orbit, with least periods 4, 8, 32, 128, 256, 1,024 from super steps 3, 7, 11, 31, 60, 163; the last 1 to 35 cycle with their least periods, the last 35 every 8.8·1016 super stepskernelcycle₁–cycle₆ (decide), lean/Cycles.lean; cycle1–cycle35 (in pieces), lean/CycleRun.lean; §6
Each further level multiplies the period by 1, 2, 4 or 5: modulo 5 the block moves by r → 3^W·r + b, and the factor is the period of its residuekernelcycle_residues, period_factor, lean/Periods.lean; §6
The last 36 to 44 blocks cycle too (the last 44 every 1.8·1021 super steps), each level multiplying the period by 1, 2, 4 or 5computedc/superrun.c, which checks each cycle before it uses it; py/cycles.py; §6
No halt in the first 2.7·1049 steps (6·1023 super steps)computedc/superrun.c, skipping over those cycles; checked against c/blkrun.c (the old bound, 3.7·1022), py/superrun.py and py/waves.py; the orbit is proved, the run is C
The last block cycles 11 → 13 → 14 → 12, so N runs odd, odd, even, evenon paperfrom the super-step formula (notes/LAB_NOTES.md); the only exact pattern found
The next return can halt only if 280 divides d1 (from orbit_grows and the top blocks at the end of the long run)computedpy/top_stats.py odds; the blocks from c/superrun.c
The law of N mod 2k at the right end, exact over a period for k ≤ 18: valuation profile tending to 1.28, next bit ever closer to a fair coin, N never 3030 or 4054 mod 212computedc/bottom2adic.c, runs/bottom2adic_18.txt; the two misses proved by the kernel, never_3030_4054 (lean/ResidueRun.lean); the top blocks, §4
No invariant in the families tried (residues, binary digits, growth bounds)computedpy/n_search.py, §7
The random model of d1 holds on the map from 60,000 random starts within a factor of about 2 at every scale up to 230 (2,018 halts, 2,024 expected)heuristicc/ensemble.c, py/top_stats.py; the top blocks, §5
The machine almost certainly never halts (chance of a future halt about 5·10−25)heuristic§7
Whether N is ever a power of twoopen

7. Why it almost certainly never halts heuristic

The wave is a binary carry. To reach the left end it needs v_2(N) ≥ m − 1, which happens about once every 2^(m−1) super steps if N's low bits behave like coin flips, and each visit adds at least one block. The low bits are not quite coin flips: from the periodic tables, a wave gets past the last k blocks at the rate 1.2764·2−k per super step, so N is divisible by 2k about 28% more often than a random number (computed; the constant is stable to four digits from k = 30 to 44). The observed gaps fit these estimates within a factor of two, so the visits do not stop; they thin out. The head reaches new tape on the left at steps 2,047,931, then 26,618,972,322, then 6.4·1010, and so on: 38 returns in the first 2.7·1049 steps (runs/superrun_long.txt).

No invariant in sight. Along the orbit (super steps 103 to 4·106), N takes every residue modulo each odd q ≤ 127 that a power of two can take, also jointly with its bit length. Its binary digits look random: the lowest digit count at each length matches random numbers, and the leading bits come within 15 zeros of a power of two. Bounds on growth cannot help on their own, since halting depends only on the sum N. The only exact pattern is at the right end: the last block cycles 11 → 13 → 14 → 12, so N is odd, odd, even, even, which says nothing about powers of two (py/n_search.py, PR #118).

At a visit, what decides is d_1, a number the size of the first blocks, now about 1.9·1024 (81 bits) and growing. If it behaved like a random integer, the chance of a power of two would be about 1/(d_1 ln 2) per visit; d_1 has grown by about 2.1 bits per visit, from 9 to 1.9·1024 over 38 visits, so the sum over all future visits is about 5·10−25. (This page first said 1027 and 10−27, from a miscounted d1; see the top blocks, §3, which also tests the random model and proves that N only grows.) The rule for the periods does not change this: it describes the settled levels at the right end completely, but d_1 is decided by the young levels at the left end, which nothing above constrains. That is a reason to expect the machine to run forever, not a proof: a proof has to show that one particular orbit never hits a power of two, a question with the flavour of the Collatz problem.

Prior work

As of 30 October 2026 the machine is an open BB(6) holdout on @mxdys's lists (623 machines up to equivalence) 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 added it on 27 October 2026 as an open acceleration problem (PR #18). Its Lean proof that the machine halts iff a map on two stacks of block lengths halts is at the level of section 2 above, cut at other moments, and its higher-level map is exactly the event map of the wave model (each time A stands on the blank right end), one level below the super step of section 4 (py/deepmind.py checks it; lean/DeepMind.lean proves it for every event). No source found goes further: the super step's formula and the criterion on N (sections 4 and 5) appear to be new.

The ledger says 1RB1RA_1RC1LB_1LD0RA_1RA0LE_---0LF_0RD0LB was merged into another equivalence class in April 2026. It runs through the same tapes as this machine and halts from the same configurations (py/sibling.py), so the reduction should hold for it too. The map is not Antihydra's or Hydra's: those iterate one integer under n → ⌊3n/2⌋ and halt when a parity count goes negative, while here the state is a growing list and N does not determine the next N. Sources and details: notes/PRIOR_WORK.md.

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                  # Rules, Macro, …, Cascade, Cycles (about 6 min)
bb6-1RB1RA_1RC1LB/lean/check_cycles.sh 35 6      # the cycles of the last 1 to 35 blocks, in pieces (about 21 CPU hours)
python3 bb6-1RB1RA_1RC1LB/tests/test_machine.py  # py/macro.py against direct simulation
python3 bb6-1RB1RA_1RC1LB/tests/test_waves.py    # the wave model and the super step (about 25 s)
python3 bb6-1RB1RA_1RC1LB/py/waves.py super 20   # the super steps, with N
python3 bb6-1RB1RA_1RC1LB/py/waves.py left 100000  # the wave's visits to the left end
python3 bb6-1RB1RA_1RC1LB/py/cycles.py 8         # the cycles of the last 1 to 8 blocks (§6)