Busy Beaver Explorer / 1RB1RA_1RC1LB / the top blocks

Where 1RB1RA_1RC1LB's halting is decided: the top blocks

1RB1RA_1RC1LB_1LD0RA_---0LE_1LC0LF_1RE0LB

The machine halts iff the number N = 10 + Σ pl·2m−l, built from its blocks of ones, is ever a power of two (the reduction, proved in Lean). The blocks at the right end are understood: they cycle. The decision is made at the other end, by the first few blocks, at the rare moments when the wave of halvings gets all the way there. This page collects what is known about those moments: one new theorem, a correction to the published odds, and tests of the random model behind them.

As of 1 November 2026. Sources: lean/Monotone.lean, py/top_stats.py, c/ensemble.c, c/ensemble_fast.c, c/bottom2adic.c, the outputs in runs/, and the entries of 30 October, 1 November and 4 November 2026 in notes/LAB_NOTES.md, all in bb6-1RB1RA_1RC1LB/.

In short

The chance of a halt was put about 500 times too low, and it is still negligible. The earlier write-ups put the chance of a future halt at about 10−27, from a deciding number "d1 ≈ 1.9·1027". The value in the run is 1,874,777,618,886,538,568,719,180 ≈ 1.9·1024 (81 bits); the digits were miscounted. Redone with the right value and the measured growth of about 2 bits per return, the same random model gives about 5·10−25 (10% to 90% over resampled futures: 5·10−26 to 1.4·10−24). heuristic

N only grows. Lean now proves that N strictly increases at every super step (superL_grows, orbit_grows). So the orbit meets each power of two at most once, and since the number of blocks is fixed between returns, the next return's d1 is larger than what the top four blocks give now: the next return can halt only if 280 divides d1. kernel for the theorem; the blocks are from the C run computed

The bet splits in two. A halt needs d1 = 2a: its 2-adic valuation must be enormous (at least 80 next time) and its odd part must be exactly 1. The 2-adic half alone, if the valuation at a return is geometric, gives 2−80 ≈ 8·10−25 for the next return. That half is the one the run lets us test, and it holds up: at the right end N's residues mod 2k settle into an exact law with a density (one residue pair mod 212 never occurs); at the left end, waves pass each of the top 24 blocks of the blank-tape orbit half the time, to three decimals where the counts allow. computed

The random model holds on the map itself to within a factor of about 2 at every scale tested. From 60,000 random starts (522,749 returns), the map halts 2,018 times against 2,024 predicted. Near-halts (odd part of d1 below 2c) can be counted up to d1 ≈ 230; they come at 0.4 to 1.4 times the predicted rate, mostly within 25%. A shortfall of about 15% in high valuations (v2(d1) ≥ 8) seen in that run turned out, on 107 starts, to be an artefact of its starting tapes, which repeat and merge: counting each return once, or starting from wider tapes, the valuations are geometric to within 1% (§5). heuristic

Still open: whether N is ever a power of two. Nothing here comes near a proof; it says where the problem sits and how much the heuristic can be trusted.

1. The returns and the top blocks

Write the tape at a super step as blocks p1, …, pm (left to right) followed by 5, 0. Each super step sends a wave left from the right end with dm+1 = 20 and dl = pl + dl+1/2; it goes on while d is even and turns at the first odd d. It reaches the left end, a return, exactly when 2m−1 divides N, and then N = 2m−1·d1. N can only be a power of two at a return, so halting is decided by d1 = p1 + p2/2 + p3/4 + …, a weighted sum that the first few blocks dominate. In 6·1023 super steps there have been 38 returns (runs/superrun_long.txt).

What a return writes. With d1 = 2s·u, u odd and not 1, the top block is replaced by s + 2 new blocks: (u−1)/2, (u+5)/2, u, 2u, …, 2s−1u. Until the next return the top block only ever gains (a wave that turns at the second block adds (d2−1)/2 to it; nothing else reaches it), so it stays at least (u−1)/2. If none of the new blocks is touched before the next return, the next value is exactly

d1' = ((s + 3)·u + 3)/4 + h/2s+1,       h = the wave arriving at the block 2s−1u

(on paper from the super-step formula; it holds at the three returns among the first 31 where all of them survive, super steps 2, 1.6·108 and 7.1·1010). So part of each d1 is written by the previous return and the rest is carried up from below. On the blank-tape orbit ((s + 3)·u + 3)/4 has been between 0.1% and 85% of the next d1.

How d1 has grown. From 9 at the first return to 1.87·1024 at the 38th (super step 3.1·1023, m = 81): 2.1 bits per return on average, 2.0 from the sixth on, with occasional drops (the 18th return, 1.33·1011, came after 3.62·1011). Its odd part has never been small: the largest valuation so far is s = 7, at the 29th return.

2. N only grows kernel

Where the wave turns at block i (di odd, j = m − i), N goes up by 10 − 2j + (di + 5)·2j−1 + Σk>i dk·2m−k−1, which is more than 2j+1. At a return it is multiplied by more than (3 + s)/2. In Lean the proof is three short inductions over the definitions of lean/Wave.lean:

leftEnd_grows: at the left end the new blocks S W are more than 3/2 of the arriving d.
wave_grows: a wave with value d and the blocks L to its left leaves blocks W with d + 2·S L < S W.
superL_grows, orbit_grows, blank_orbit_grows: N strictly increases at every super step, so along the orbit from blank tape it is strictly increasing.

Standard axioms only (lean/Axioms.lean), checked by lean/check.sh. Two consequences:

  • Each power of two is passed once. N either lands on it or jumps over it, and is then above it for good.
  • A floor for the next return. Between returns m does not change, so the next d1 = Nthen/2m−1 is larger than Nnow/2m−1 ≥ p1 + p2/2 + p3/4 + p4/8. At the end of the long run (super step 6·1023) the top blocks are 234347202360817321089897, 234347202360817321089900, 2163436398666026041512949 and 2273252587298508113309726, so the next d1 exceeds 1.18·1024 = 279.96: a halt at the next return needs d1 = 2a with a ≥ 80 (python3 py/top_stats.py odds; the blocks rest on c/superrun.c).

This does not bound the odds by itself, since nothing stops d1 from being 280. It turns "is d1 ever a power of two" into a sharper statement about one number: at the next return N must be divisible by 2m−1+80.

3. The odds, corrected heuristic

If d1 behaved like a random integer of its size, it would be a power of two with probability about 1/(d1 ln 2). The earlier estimate summed this over future returns starting from d1 ≈ 1.9·1027 (91 bits) and 2.4 bits of growth per return, and got 10−27. Both inputs were off: d1 is 1.9·1024 (81 bits; log2 = 80.63), and the growth is 2.1 bits per return.

estimatewhat it assumeschance of a halt
earlier write-upsd1 = 1.9·1027, +2.4 bits per return10−27 (wrong input)
random model, correctedthe next d1 above the floor of §2, then the 37 observed increments of log2 d1 resampled (20,000 futures)median 4.4·10−25, mean 6.5·10−25; 10% to 90%: 4.7·10−26 to 1.4·10−24
the 2-adic half alone, next returnv2(d1) geometric at a return; only the floor 280 used2−80 ≈ 8·10−25

Counting time instead of returns gives the same order: a halt needs N = 2a, a random N near x is a power of two with probability 1/(x ln 2), and N grows like (super steps)2.06 on this orbit, which sums to a few times 10−25 after the last return. Whichever way it is counted, the machine runs forever unless the orbit is special. The rest of the page asks whether there is any sign that it is.

4. The 2-adic half: N's low bits, from the right end to the left computed

At the right end the law of N mod 2k is exact. N mod 2k depends only on the last k blocks, and those run on their own and cycle (proved for k ≤ 30). Over one period of the last 18 blocks (1,048,576,000 super steps, from the tape at super step 109; c/bottom2adic.c, runs/bottom2adic_18.txt) the time averages are therefore exact for all later times:

  • The valuation. v2(N) = j occurs 1, 0.5, 1.25, 1.75, 2.13, 1.44, 1.28, … times as often as 2−(j+1) for j = 0, 1, 2, …, then hovers near 1.28: the factor 1.2764 by which deep waves are more frequent than coin flips (the reduction, §7).
  • The next bit is a fair coin, more and more. Given the bits below, the next bit of N is 1 with probability off from 1/2 by 0.07 on average at bit 4, 0.017 at bit 9, 0.0045 at bit 15 and 0.0018 at bit 17. So the law of N in the 2-adic integers settles to one with a density: no residue class mod 2k gets more than 3.5 times its uniform share, however large k.
  • One missing pattern, and why. N is never 3030 or 4054 mod 212 (binary 1?1111010110), and no other residue mod 218 is missed; Lean's kernel now proves the first part for every super step after the last 12 blocks settle (never_3030_4054). Both are the end of one thin branch, the 2-adic class of −42: 22, 86, 214, 470, 982, 2006, 4054 are −42 mod 2k, and this class is the rarest mod 2k for k = 5 to 11, with 5 visits per period of the last 12 blocks mod 210 where 320 would be uniform. Half of it is exact: N ≡ 2 mod 4 only when the last two blocks are (12, 26), one super step in eight instead of one in four (mod4_blank), and three steps later N is larger by exactly 106 (plus106), so the thin class is that of the waves from (14, 42) that go exactly seven blocks deep. The rest belongs to this orbit: from random tapes the last blocks settle into other cycles of the same map, which starve other classes (22 mod 32 gets 0 to 1.9 times its share there) and some miss whole classes mod 28 (py/top_stats.py branch, cycles). It says nothing about powers of two: they are 0 mod 2k, which means a wave crossing the last k blocks, and a cycle that never gives that is a silent level, already a proof of no halt; on this orbit 0 mod 2k gets more than its share.

At the left end the waves pass each block half the time. On the blank-tape orbit, after super step 106 and up to 1017, a wave that reaches the k-th block from the left has d even there (and goes on) with these frequencies (python3 py/top_stats.py toppass 1e17, runs/toppass_1e17.txt):

block from the left1 (d1 even)2346812162024
waves reaching it1932601144541,80229,648365,8653,586,1245,816,398
fraction that pass0.530.590.530.530.4960.4980.4970.50060.50000.4998

So on this orbit the wave behaves as a sequence of fair coins all the way up to the top block, the young blocks included. The valuation s = v2(d1) at a return continues the same coin flips through the "blocks of 0" beyond the left end, and a halt next time needs at least 80 of them in a row. Its 38 values so far (mean 1.0, largest 7) look like a geometric law, but they are too few to test the tail; for that, the map has to be run from many starts.

5. The random model, tested on the map computed heuristic

c/ensemble.c runs the super step for 224 super steps from each of 60,000 random starts (2 to 4 blocks of 1 to 100) and records every return: 522,749 returns, d1 up to 230 (runs/ensemble_summary.txt, python3 py/top_stats.py ensemble). The earlier test from 3,600 starts [a, b] found 217 halts against about 239 expected.

log2 d1345678910111213–15all ≥ 3
halts2775252612708200823810682,018
expected38.1133.0396.9739.6466.2146.455.525.011.85.64.82,023.7
ratio0.710.560.630.831.521.371.481.520.851.071.70.997 ± 0.022

Halts follow 1/(d1 ln 2) overall and within a factor of 1.8 in every bin; small values carry the most weight and wobble the most. Above d1 ≈ 215 a halt is too rare to count, so the tests below look at the things a halt is made of.

  • Near-halts. A halt is "odd part u = 1". The random model gives (2c/2)/(d1 ln 2) returns with u < 2c, which can be counted at every scale. Over c = 1 to 20 and d1 from 28 to 230, the observed counts are 0.4 to 1.4 times that wherever at least 20 are expected; pooled over sizes, 1.38 at c = 1, 1.20 at c = 2 and 0.76 to 1.09 for c = 3 to 20, against 0.9 to 1.0 for random numbers of the same sizes run through the same count (c ≥ 5).
  • The valuation. P(v2(d1) ≥ t) is 2−t to within 3% for t ≤ 7 in every size band. Beyond, this run fell short: pooled over d1 ≥ 216, 0.89, 0.85, 0.87, 0.84 of 2−t for t = 8 to 11 (about 3σ at t = 8 and 9). The larger test below shows that this comes from the starting tapes, not from the map.
  • Residues. d1 mod q for odd q from 3 to 31 puts 0.98 to 1.00 of the uniform share on the residues of powers of two. The odd part mod 28 is close to uniform but measurably not (frequencies 0.9 to 1.15, significant even with one return per orbit), and u ≡ 1 mod 28 gets 0.81 to 1.04 of its share, depending on the size band.
  • Leading bits. The fractional part of log2 d1 is uniform to within 3%, and 2.00% of returns lie within 0.01 of a power of two (2% expected).

So the map is not a perfect random-number generator, but every departure found is within a factor of about 2. Nothing seen would change the order of magnitude of §3.

The shortfall in high valuations, tested on 107 starts (1 November 2026). c/ensemble_fast.c runs the same orbits as c/ensemble.c (it prints exactly the same returns, checked in the tests) but tabulates the bottom levels once they cycle, as c/superrun.c does, so an orbit of 224 super steps takes about half a millisecond instead of 65. The ratio below is the observed number of returns with 2t dividing d1 over the number the random model expects, pooled over d1 ≥ 216 (runs/valuation_test.txt). heuristic

starts (orbits of 224 super steps unless noted)returns countedt = 8t = 10t = 12halts with d1 ≥ 216
107, 2–4 blocks of 1–100 (the old design)87,106,7400.901 ± 0.0030.865 ± 0.0050.743 ± 0.01246 / 112.0
the same, each return counted once13,267,3990.999 ± 0.0070.984 ± 0.0140.964 ± 0.03026 / 16.6
107, 4 blocks of 1–100, each return once22,603,2660.998 ± 0.0060.987 ± 0.0110.987 ± 0.02341 / 27.6
107, 2–4 blocks of 1–10482,246,4141.000 ± 0.0031.006 ± 0.0061.002 ± 0.012155 / 109.9
107, 2–8 blocks of 1–10670,690,0201.000 ± 0.0020.998 ± 0.0040.995 ± 0.00889 / 86.7
105 of 1014 super steps, the old design, each return once1,016,8060.969 ± 0.0190.969 ± 0.0381.04 ± 0.080 / 0.7
2·105 of 1014 super steps, 2–8 blocks of 1–1062,727,3090.988 ± 0.0101.006 ± 0.0191.004 ± 0.0393 / 1.7

The shortfall is real in the old design and comes from its starts. With 107 fresh starts it comes back, far beyond noise (36σ at t = 8), but it swings from one return to the next (by the return's number in its orbit, the ratio at t = 8 runs from 0.26 to 5.7). Two blocks of 1 to 100 make only 104 different tapes, drawn a third of the time, and orbits from different starts merge: 74 of the 87 million returns repeat an earlier return (the same d1, number of blocks and blocks below the top). So a few thousand histories are counted thousands of times each. Counting each return once (-u) removes the shortfall, and starts that neither repeat nor merge never show it, up to orbits of 1014 super steps with d1 past 240. What is left is at most a few percent for t up to 12, within two standard errors in every run, and a factor like that does not move the odds of §3. Halts above 216 come at 1.0 to 1.6 times the model rate once repeats are removed (on counts of 26 to 155).

The near-halt counts above used (2c/2)/(d1 ln 2) per return, which is only approximate when d1 is not far above 2c. py/top_stats.py fast uses the exact chance that a d1 of its bit length has odd part below 2c under the 1/(d1 ln 2) density; with it, the wide starts give 0.97 to 1.01 for c = 4 to 20.

6. What this gives, and what is left

Proved: N strictly increases (lean/Monotone.lean), so each power of two is met at most once, and with the C run's blocks the next return can halt only if 280 divides d1.

Exact but computed: the law of N mod 2k at the right end, k ≤ 18 (and for k ≤ 30 it follows from the proved cycles in the same way); the pass rates at the top of the blank-tape orbit.

Heuristic: the odds of a future halt, about 5·10−25, and the evidence that the random model behind them holds within a factor of about 2 wherever it can be tested.

What a proof would need is still an argument that one orbit avoids one thin set, and nothing here supplies it. Two partial results look within reach. (1) An exact version of the right-end law for every k: the 2-adic law of N exists and has a density bounded by a constant. This would follow from the period rule if the residues the levels settle on could be controlled. (2) A deterministic bound on the valuation at a return in terms of the top blocks, which would turn "280 divides d1" into an impossibility for the next return. The shortfall in high valuations once seen from random starts is no help here: on 107 starts it turned out to come from repeated and merging starting tapes, not from the map (§5).

Check it yourself

bb6-1RB1RA_1RC1LB/lean/check.sh                 # includes Monotone.lean (about 6 min)
python3 bb6-1RB1RA_1RC1LB/tests/test_top.py     # the tools below against py/waves.py (seconds)
cd bb6-1RB1RA_1RC1LB
python3 py/top_stats.py odds                    # the floor for the next return and the corrected odds
python3 py/top_stats.py toppass 1e17            # pass rates at the top of the blank-tape orbit (about 30 s)
gcc -O2 -o bottom2adic c/bottom2adic.c -lm
./bottom2adic 18 1000000000 1048576000 $(tail -1 runs/superrun_checkpoints.txt | awk '{for(i=NF;i>2;i--) printf "%s ",$i}')
gcc -O2 -o ensemble c/ensemble.c
./ensemble 10000 16777216 100 2 4 100 0 > e0.txt   # one of the ensemble runs (about 20 min)
python3 py/top_stats.py ensemble e0.txt
gcc -O3 -march=native -o ensemble_fast c/ensemble_fast.c
./ensemble_fast 250000 16777216 1000 2 4 100 0 > f.txt   # a fortieth of the 10^7-start test (about 2.5 min)
./ensemble_fast -u 250000 16777216 1000 2 4 100 0 > u.txt   # the same, each return counted once
python3 py/top_stats.py fast f.txt; python3 py/top_stats.py fast u.txt