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.

  1. At a glancethree kinds of evidence
  2. 1 · The pass mapwhy a halt needs a 1
  3. 2 · How far2^62 proved, 2^74 computed
  4. 3 · The invariant psione exact quantity
  5. 4 · Routes that failedand their counterexamples
  6. 5 · The final reductionevery a = 5 mod 12
At a glance

Proved, computed, heuristic

Lean, kernel
  • 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.
computed
  • 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.
heuristic
  • 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.
Part 1

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.

Lean, kernel The machine follows the closed form for every block list, and halts exactly where the form says it does.
pass, pass_halt in lean/Pass.lean
Lean, kernel A pass adds exactly 4 ones, so pass n from blank tape has 4n ones. A halt needs every block but the last to be even and the last odd, so a halting list has an odd count. The only way the count can stop being a multiple of 4 is a sweep that stops at a block of a single 1, which the form does not cover. So if the machine halts, some pass stops at a block of 1.
next_sum, next_halt_odd, halts_only_by_one
Lean, kernel Every block after the first stays at least 2, so the block of 1 can only be the first block, after the sweep has crossed all the others. And two passes in a row never both stop at the first block. So a halt needs the first block to be halved down to 1, about log2(ones) halvings, without the rest of the list getting in the way.
next_good, one_front, front_twice, halts_only_at_front in lean/Front.lean
Part 2

How 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.

Lean, kernel For every a ≡ 1 (mod 4) with 5 ≤ a < 262, the excursion from [a, 2a+1] returns. So the first 3·260+1 ≈ 3.46·1018 passes never stop at a block of 1, and the machine really reaches each of their pass starts. The proof runs the map on residue classes of a and is split into 1,575 pieces checked by the kernel, about an hour of CPU.
returns_2_62_kernel, no_one_3e18_kernel in lean/Return62.lean; the same statement with Lean, native_decide in seconds (no_one_3e18)
computed The same class computation in Python, run down to residues mod 274, finds every excursion for 5 ≤ a < 274 safe. With the Lean reduction that gives no halt in the first 1.4·1022 passes. This rests on trusted Python (tested against Lean's next), not on a proof.
py/returnmap.py
computed Independently, the machine runs 1011 steps without halting, and the closed form, iterated one pass at a time in C with no residue classes, runs 1011 passes without a block of 1. After pass 50 no sweep stops at a block below 59.
tools/c/tmrun.c, c/passorbit.c
Lean, kernel With no upper bound on a: every a ≡ 1 (mod 4) returns unless a mod 234 is one of 67 residues, a fraction 1.6·10−8. A failure, if any, lives in a very thin set.
returns_off_open34 in lean/Thin.lean
Part 3

The invariant psi

One exact quantity survives a pass. With the blocks read from the last one back,

ψ = yk − 2yk−1 + 4yk−2 − 8yk−3 + …
2ψ' = −ψ + 3(−2)n − 7,   n ≤ k the number of blocks the sweep crosses
Lean, kernel The rule above holds for every pass of every list. On a two-block state [a, 2a+d] it is just d.
psi_next in lean/Psi.lean
computed On the first 108 passes, and on every excursion class down to mod 266, psi stays in −21..24 with at most 6 blocks.
py/invsearch.py
heuristic Each pass roughly halves psi and adds a term set by how many blocks the sweep crosses, so psi is pulled back toward a small range. It ends the simple halving loops of the first block within about log4|psi| rounds. With at most 6 blocks it bounds the run of halvings, which was the hope of a proof. Part 4 shows why that hope did not hold.

A 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.

Lean, kernel next(φ(y)) = φ(next(y)) for every list, halts and stops at a block of 1 included. From the tape 15 0 13 the pass map runs φ of the blank-tape orbit for ever, and [x, 2x+6, 3] runs exactly the excursion of [x, 2x+1].
next_phi, sentinel_orbit, inner_counter in lean/Sentinel.lean
computed A last block that is 3 only modulo 2r works the same way for about r passes. So for a = 1 + 2mu the excursion from [a, 2a+1] replays the blank orbit, modulo a power of 2 that loses a bit per pass, for its first m − 1 passes (checked up to m = 3·104), with its first block above a/4. The run reads its own beginning at the scale log a.
py/sentinel.py deep
Lean, kernel The replay holds for every m and u: a pass keeps “each block at least the reference block, and equal modulo 2Q” as “modulo Q”, so the excursion of a = 1 + 2mu follows φ of the blank orbit for m passes, and its first min(m, 3·260+2) passes never halt or stop at a block of 1.
next_rel, replay, replay_3e18_kernel in lean/Replay.lean, lean/Replay62.lean
Part 4

Routes 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_twice give 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.

Part 5

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.

Lean, kernel If every a ≡ 5 (mod 12) has an excursion that returns (with a jump that skips no value ≡ 1 mod 32), no pass ever stops at a block of 1, so the machine never halts.
no_one_of_all in lean/Visit.lean
Lean, kernel If some a ≡ 5 (mod 12) fails, the least one has its residue among the 67 open ones mod 234, the counter cannot step over it, and the blank orbit reaches [a, 2a+1] for that a.
skip_off_open34, visit, orbit_meets_first_failure
computed Going backward gives nothing either: every list has many preimages (1,333 for pass 1,000), so ancestry from blank tape is no constraint.
py/ancestry.py
open So the machine runs forever if every a ≡ 5 (mod 12) has an excursion that returns, and a halt has to come from the first a whose excursion fails. Any failure sits above 262 (proved) and above 274 (computed), inside 67 residue classes mod 234.
heuristic Why it looks Collatz-hard. An excursion reads only a few low bits of a, but the a not yet covered form a 2-adic set of dimension about 0.19, and on that set the bits of a mix the way they do in the Collatz map, with no repeating pattern. Deciding whether every a returns is a statement about all digit patterns of that set. Near a = 1 the deepest excursions repeat the same map one level down, a counter inside a counter. A finite table cannot settle it; a proof needs an inequality carried by induction over the excursion, and no candidate has survived Part 4.
py/dynamics.py, py/induction.py; notes/LAB_NOTES.md, 31 October and 1 November
open An induction for the excursion from [a, 2a+1], for a ≥ 262, that shows no sweep ever stops at a block of 1, and so the question itself.