Busy Beaver Explorer / 1RB1RA_1RC1LB_1LD0RA_1LB0LE / what is known
What is known so far
1RB1RA_1RC1LB_1LD0RA_1LB0LE_1LF1LD_---0LD
Whether this machine halts from blank tape is open. This page sums up where the work stands as of 2 November 2026. The run reduces to a map on block lists, a halt needs one rare event, that event is ruled out for an astronomically long stretch, and every attempt to rule it out for good has hit a counterexample. What is left looks as hard as a Collatz problem.
Every claim carries a tag for what it rests on: Lean, kernel checked by Lean's kernel alone, Lean, native_decide also trusts Lean's compiler, computed by C or Python in the repository, exhaustive but not proved, heuristic sampling, a pattern seen so far, or an argument that is not a proof. For the mechanics, see the interactive explainer; for theorem names and file paths, the proof-status page.
Proved, computed, heuristic
- The run is a sequence of passes, and one pass is a closed-form map on block lists, for every list.
- A halt needs a sweep that stops at a block of a single 1, and that block can only be the first block.
- No such stop in the first 3·260+1 ≈ 3.46·1018 passes.
- The exact rule for psi under a pass.
- A block of 3 at the right end makes the pass map run a copy of itself: the orbit of φ(y) is φ of the orbit of y.
- For every a = 1 + 2mu the excursion from [a, 2a+1] replays the blank orbit for m passes, so its first min(m, 3.46·1018) passes are safe.
- Counterexamples to four proof routes.
- If every a ≡ 5 (mod 12) returns, the machine never halts; if one fails, the blank orbit reaches the first failure.
- No halt in the first 1011 machine steps.
- The return map is safe for every a below 274, so no halt in the first 1.4·1022 passes.
- 1011 passes followed one by one never meet a block of 1.
- On the orbit psi stays in −21..24.
- The orbit keeps a wide margin: the first block stays above 0.7% of the ones.
- The blank orbit is expected to reach 7 blocks near pass 2221.6, and no fixed cap on the block count is expected.
- The remaining question, about all digit patterns of a 2-adic set, looks Collatz-hard.
The pass map, and the one way to halt
From step 17 on, the run is a sequence of passes. At a pass start the tape is a list of blocks of ones [y1, …, yk] separated by single zeros. The head sweeps left, halving each block it crosses, stops at the first odd block, then zigzags back to the right end. The result is a closed-form map next on block lists. The explainer animates one pass.
pass, pass_halt in lean/Pass.leannext_sum, next_halt_odd, halts_only_by_onenext_good, one_front, front_twice, halts_only_at_front in lean/Front.leanHow far it is ruled out
The orbit keeps coming back to two-block states [a, 2a+1] with a ≡ 5 (mod 12); pass 4 is [5, 11]. The passes between two such visits are an excursion. An excursion that comes back lands on [a+12k, 2(a+12k)+1] after exactly 9k passes, so the return map a → a+12k is a counter that only goes up. If every excursion up to some size comes back, every pass up to a matching point is safe.
returns_2_62_kernel, no_one_3e18_kernel in lean/Return62.lean; the same statement with Lean, native_decide in seconds (no_one_3e18)next), not on a proof.py/returnmap.pytools/c/tmrun.c, c/passorbit.creturns_off_open34 in lean/Thin.leanThe invariant psi
One exact quantity survives a pass. With the blocks read from the last one back,
psi_next in lean/Psi.leanpy/invsearch.pyA second exact fact found later: with φ(y1 … yk) = y1 … yk−1 (yk+5) 3, a block of 3 at the right end is always crossed and always stays 3, so the pass map run on φ(y) is the pass map run on y.
next_phi, sentinel_orbit, inner_counter in lean/Sentinel.leanpy/sentinel.py deepnext_rel, replay, replay_3e18_kernel in lean/Replay.lean, lean/Replay62.leanRoutes that failed, and their counterexamples
Each route below tried to show that the first block cannot be halved down to 1. Each one is refuted by a block list that the kernel checks: the list satisfies everything the route would know about the orbit (4 divides the ones, every block after the first at least 2, small psi), and still reaches a first block of 1. Lists are written first block first.
Bound the block count by 6
- The idea
- With at most 6 blocks, psi and
front_twicegive a finite graph that allows at most 9 front stops in a row, so a first block of 1 would need a change that left it at most 511 computed. - Counterexample
- From [a, 2a+1] with a = 2203 + 2221 + 1 (a ≡ 5 mod 12) the machine reaches a pass start with 7 blocks after 204 passes Lean, kernel. The classes to mod 266 missed it because it needs a mod 2222. The blank orbit cannot step around it either: if it ever reaches [a, 2a+1] within 200 returns below this a, it walks up to it Lean, kernel, so it is expected to have 7 blocks near pass 2221.6 heuristic.
seven_blocks in lean/Seven.lean; window_seven in lean/Window.lean
A second invariant beside psi
- The idea
- Find a second exact quantity that, with psi, bounds the front stops between changes of the first block. Up to 6 blocks, the (k, psi) graph bounds them by 17 computed.
- Counterexample
- From 7 blocks the graph has a front-stop cycle. The list [31, 96, 64, 32, 88, 162, 235] (psi = −57) follows it, halving its first block 31 → 1 and stopping at a block of 1 on its ninth pass; a second list does the same from 255 Lean, kernel. A second invariant would have to be false on these lists, and no fixed weighting of the blocks works.
lean/Run7.lean; py/runbound.py
Only a few large blocks
- The idea
- Along the orbit at most 5 blocks are ever at least ones/32 computed, so the counterexamples above, with many medium blocks, might not be the orbit's shape.
- Counterexample
- Adding 28·v with psi(v) = 0 to the lists above gives [31, 254304, 870464, 844832, 256088, 32930, 8427] and one from 255. They keep psi = −57, have at most 5 large blocks at every pass start, and still halve the first block to 1 and stop there Lean, kernel.
wL_one, wL_large, wLb_one, wLb_large in lean/Large.lean
A large first block
- The idea
- The lists above have a tiny first block (1.4·10−5 of the ones), while the orbit leaves it at least 7.6% of the ones at every change and runs at most 5 front stops after computed. Maybe a big first block cannot be halved to 1.
- Counterexample
- [255, 512, 32, 60, 32, 64, 9] (psi = −23, first block 26% of the ones) and [255, 528, 48, 24, 8, 32, 64, 128, 129] (psi = 1, 21%) halve their first block 255 → 1 with no other change and stop at a block of 1 Lean, kernel. Such lists exist for every run of 4 to 8 halvings computed, and a count of parity bits suggests the same for longer runs heuristic.
wF_one, wH_one in lean/BigFront.lean
Two broader negative results sit behind these. No invariant of block sizes or of residues modulo a fixed power of 2 can exclude the event, since small starts reach it by a halving loop heuristic. And with the parities left free, the reachable lists halve their first block every two passes, so an induction on sizes alone cannot work: a proof has to say which parities occur computed.
The final reduction
The last hope was structure that holds only along the blank orbit, since it starts from one tape and not from every list. There is none beyond a mod 3: the orbit meets the first failure, whatever it is, so the question for the orbit is the question for every a.
no_one_of_all in lean/Visit.leanskip_off_open34, visit, orbit_meets_first_failurepy/ancestry.pypy/dynamics.py, py/induction.py; notes/LAB_NOTES.md, 31 October and 1 November