Busy Beaver Explorer / 1RB1RA_1RC1LB_1LD0RA_1LB0LE

What is known about 1RB1RA_1RC1LB_1LD0RA_1LB0LE, and what is open

1RB1RA_1RC1LB_1LD0RA_1LB0LE_1LF1LD_---0LD

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. (It shares its first three states with 1RB1RA_1RC1LB_1LD0RA_---0LE_1LC0LF_1RE0LB, which has its own page; the two are different machines.)

The run is made of passes, and a pass is a map on the lengths of the blocks of ones. The closed form of that map is proved in Lean for every block list, and with it the reduction: the machine halts only if some pass's sweep stops at a block of a single 1. The explainer runs the machine, its passes and the closed form in the browser.

Status as of 5 November 2026.

In short

The question is open. Lean proves no halt in the first 20,000 steps by the kernel alone and in the first 107 steps with native_decide; the C simulator finds no halt in the first 1011 steps.

Where it stands. At the start of each pass the tape is 1^y1 0 1^y2 0 … 0 1^yk A>0. Lean's kernel proves the closed form of the pass map for every block list, that a pass adds exactly four ones, that a halt needs the last block odd and all others even (so an odd number of ones), and from these the reduction: if the machine halts from blank tape, the orbit of block lists reaches a pass whose sweep stops at a block of a single 1 (halts_only_by_one). Iterated one pass at a time for 1011 passes it never does: after pass 50 no sweep stops at a block below 59, and the lists have 2 to 6 blocks, all of them a fixed fraction of the tape except a tail that halves each pass.

The return map, now a theorem. Every two-block state [a, 2a+d] with |d| ≤ 3 leads in at most three passes to one with d = 1 (Lean, every a ≥ 5), and from [a, 2a+1] the orbit comes back to [a+12k, 2(a+12k)+1] after 9k passes. Lean's kernel checks this return for every a = 1 mod 4 with 5 ≤ a < 262, by running the pass map on residue classes of a with a symbolic evaluator that is itself proved to agree with the pass map. With the reduction: the first 3·260 ≈ 3.46·1018 passes never stop at a block of 1, and the machine reaches every one of their pass starts (no_one_3e18_kernel, kernel only). Whether the machine halts is now a question about the excursion from [a, 2a+1] for a ≥ 262, and the route list there is infinite, so this way of checking cannot settle it. The same computation in Python reaches 274 (1.4·1022 passes, trusted).

Is it Collatz-like? Not at the level of the return map: G only adds 12k (k ≥ 1), so its orbit is a counter that runs through about 95% of all a = 5 mod 12 in order, and the question is not where one orbit goes but whether every excursion is safe, a statement for all a. Inside the excursions there is Collatz-style mixing, but only on a thin 2-adic set (dimension about 0.19), and with a wide margin: on every route checked a stop block is at least about a/64, where a stop block of 1 needs about 1/a. So a proof would have to be an inequality on the stop blocks proved by induction, not a finite case analysis.

Collatz-hard, by the evidence so far. Every local route (block count, a second invariant beside ψ, few large blocks, a large first block) is beaten by lists that keep ψ and every other known invariant, and the orbit has no structure of its own to add: every list has many preimages, the return map's jumps never skip a value = 1 mod 32, every open residue is 1 mod 256, and so the blank orbit reaches the least failing a = 5 mod 12 if there is one (orbit_meets_first_failure, kernel). The question for the orbit is the question for every a = 5 mod 12: a statement about all digit patterns of a positive-dimension 2-adic set, which holds with a wide margin heuristically, as Collatz does, and for which no proof method is known.

The pass

A pass starts with A on the blank cell right of the tape. A, B and C write three ones and D turns back (start). D and E then run left writing 0 and 1 in turn (de_sweep), halving the last block into (10)^m. Where E reaches a 0 between blocks it crosses into the next block on the left (e_cross), unless that block is empty: then F reads a 0 and the machine halts. Where D reaches one, the sweep ends (d_stop), and A, B and C zigzag back to the right end, each round absorbing a 0 1 and moving a 0 one cell right (zig), until C meets a 0 at the right end and the next pass begins.

So the last block is crossed if it is odd, the blocks before it are crossed while they are even, and the sweep stops at the first odd one, yj. The closed form (py/passmap.py): if yk = 2m is even, the last block goes and the two before it each gain m+2; if yk is odd, yj-2 gains (yj−1)/2, yj-1 gains (yj+1)/2 + hj+1, and the blocks from yj on become hj+1+hj+2, …, hk-1+hk, hk−1, with hi = yi/2 and hk = (yk+5)/2. The blank on the left counts as empty blocks. A stop block yj = 1 is the one case outside the form, and there the count of ones changes by an odd number.

What each result rests on

kernel checked by Lean's kernel alone native evaluated by compiled code trusted C or Python in the repository, exhaustive heuristic sampling, extrapolation, patterns open not known

kernel Proved in Lean, kernel-checked

The halting configurations

The machine stops exactly in state F reading a 0, and 0 E>0 halts after one more ordinary step, whatever the rest of the tape.

step_none_iff, halt_shape, lean/Blank.lean

No halt in the first 20,000 steps

The list simulator of the shared library, proved to agree with the machine's semantics, runs 20,000 steps from blank tape without a halt, evaluated by Lean's kernel. At step 17 the tape is 1^2 0 1^2 A>0, the first pass start (blank_at_17).

blank_runs_20000, blank_at_17, lean/Blank.lean

The pieces of a pass, for every length

Each phase of a pass as a theorem about any tape around it and any block length: the start, the D/E sweep over an odd or even stretch, the crossing into the next block, the end of the sweep, one round of the zigzag, and the A and B sweeps. Proved along symbolic runs (single steps by rfl, repeats by the shared crossing lemmas).

start, de_sweep, de_sweep_odd, e_cross, d_stop, zig, a_sweep, b_sweep, d_stop_empty, zig_empty, turn, lean/Rules.lean

The closed form of a pass, for every block list

The pass map is defined in Lean (next, with the sweep, the stop and the zigzag as sweep, bump and zag), and the machine follows it: from the pass start of any block list it reaches the pass start of next of it, and it halts whenever next says halt. Every block list, every length; the zigzag and the sweep are inductions on top of the pieces. The only case left out is a sweep that stops at a block of a single 1.

pass, pass_halt, lean/Pass.lean

The reduction to a stop block of 1

A pass adds exactly four ones and keeps every block nonempty (next_sum); a halting pass needs an odd count of ones (next_halt_odd). So pass n from blank tape starts with 4n ones and no pass halts (orbit_ok, orbit_ne_halt), and if the machine halts from blank tape then some pass of the orbit stops at a block of a single 1 (halts_only_by_one). Kernel only; the standard axioms (propext, Quot.sound, Classical.choice), no native_decide.

halts_only_by_one, never_halts_of_no_one, lean/Pass.lean

The stop block of 1 can only be the first block

Every block after the first stays at least 2 (next_good, orbit_good), so a sweep stops at a block of 1 only at the first block, after crossing every other one (one_front). With a count of ones divisible by 4, two passes in a row never both stop at the first block (front_twice): both would force 2 mod 4 ones. So if the machine halts, some pass start is 1 0 1^e 0 … 0 1^b A>0 with every e even and b odd, and the pass before did not stop at its first block (halts_only_at_front). Kernel only, no native_decide. No invariant was found that excludes the first block falling to 1.

halts_only_at_front, lean/Front.lean, tests/test_front.py

The short chains between two-block states, for every a

From [a, 2a+d] with a ≥ 5 in the right class mod 4: d = 0 goes to −2, −2 to −1, 2 to −3 (one pass each), −1 to 1 and 3 to 2 (two passes), −3 to 0 (three passes), with a growing by 2, 1, 3, 2, 3, 3. So every two-block state reaches one with d = 1. Proved for every a by running Lean's pass map on the class a = p + 4u symbolically (srunN, proved sound by srunN_ok).

chain_0, chain_m2, chain_2, chain_m1, chain_3, chain_m3, lean/Return.lean

The return map G(a) = a + 12k, for every a below 262

For every a = 1 mod 4 with 5 ≤ a < 262, Lean's pass map takes [a, 2a+1] to [a+12k, 2(a+12k)+1] in exactly 9k passes, k ≥ 1 (Returns). How: snext is the pass map on values p + q·u, failing wherever a parity or a comparison is not the same on the whole class, and snext_ok proves it agrees with next at every u. explore runs a class, splits it by the parity of u, sets the single value u = 0 aside to run concretely, and runs the one member below 262 of each class left at mod 262; explore_ok proves that when it says yes, every member returns. One kernel decide on the whole class runs out of memory, so lean/return62.py cuts it into 1,575 subclasses, each checked by decide +kernel in its own theorem (8 files, lean/R62/), and Cov.split puts them together. About an hour of CPU (17 minutes on 4 cores); lean/check_return62.sh, its own CI workflow. The same computation by native_decide (returns_2_62) takes seconds and is in the regular check, and the kernel alone does a < 216 there (returns_2_16). The Python run (py/returnmap.py classes 60: 19,231 routes, k = 1 to 11) agrees.

returns_2_62_kernel, lean/Return62.lean; explore_ok, snext_ok, lean/Return.lean

No stop block of 1, and no halt, in the first 3.46·1018 passes

Pass 4 from blank tape (counting blank tape as pass 0, so pass n has 4n ones) is [5, 11]. A pass start [a, 2a+1] has 3a + 1 = 4n ones, so a = 1 mod 4 and a < 262 while 4n ≤ 3·262; the return map then gives a later pass start of the same shape, and a later block list means every earlier pass was a block list too (orbit_ok_upto). So every pass n ≤ 3·260 + 1 is a block list with 4n ones, never a stop block of 1, and the machine reaches its pass start (reach_upto, from pass). Kernel only: propext, Quot.sound, Classical.choice.

no_one_3e18_kernel, lean/Return62.lean; orbit_ok_upto, reach_upto, lean/Return.lean

For every a: a failing excursion lies in a thin 2-adic set

With no upper bound on a: the class search of Return.lean, stopped at a depth limit without running the members of the open classes, returns their residues (thin), and thin_ok proves that an a whose excursion from [a, 2a+1] does not come back to [a+12k, 2(a+12k)+1] has its residue among them. So every a = 1 mod 4, a ≥ 5, returns unless a mod 234 is one of 67 residues, a fraction 1.6·10−8 of them. Kernel only (40 s). It does not settle the machine: the open set is infinite at every depth and contains a = 1.

returns_off_open34, thin_ok, lean/Thin.lean

The blank orbit meets the first failing excursion

For every a, unless a mod 234 is one of the 67 open residues, the excursion from [a, 2a+1] returns and its jump a → a + 12k skips no value = 1 mod 32 (thinS is thin with that check, proved sound). Every open residue is 1 mod 256. So the counter cannot step around a value = 5 mod 12, = 1 mod 32, and if some a = 5 mod 12 fails (halts, meets a stop block of 1, never returns, or jumps over a value = 1 mod 32), the blank orbit reaches the least such a; if none fails, no pass stops at a block of 1. Beyond a mod 3 the orbit has no structure of its own along the return map, so the question for the orbit is the question for every a = 5 mod 12. Kernel only.

skip_off_open34, visit, orbit_meets_first_failure, no_one_of_all, lean/Visit.lean

A second exact quantity, ψ

For every block list, the alternating sum ψ = yk − 2yk−1 + 4yk−2 − … moves by 2ψ′ = −ψ + 3(−2)n − 7 in a pass, where n ≤ k is the number of blocks the sweep crosses. On a two-block state [a, 2a+d], ψ = d. It carries the parity information a bound on sizes alone lacks: the halving loop that takes small starts to a stop block of 1 needs |ψ| large, while along the orbit ψ stays in [−19, 24] (computed, first 3·106 passes). Kernel only.

psi_next, lean/Psi.lean, tests/test_induction.py

A sentinel block of 3: the pass map contains a copy of itself

With φ(y1 … yk) = y1 … yk−1 (yk+5) 3, a pass commutes with φ for every block list, halts and stops at a block of 1 included, so the orbit of φ(y) is φ of the orbit of y. From 1^5 0 1^3 the pass map runs φ of the blank-tape orbit for ever, and meets a stop block of 1 exactly when the blank orbit does; the state [x, 2x+6, 3] runs exactly the excursion of [x, 2x+1], with the same return value and the same number of passes. So the “sentinel orbit from [1, 3]” found near a = 1 on 1 November is the blank orbit itself. Kernel only.

next_phi, iter_phi, sentinel_orbit, sentinel_one_iff, inner_counter, lean/Sentinel.lean, tests/test_sentinel.py

For every a, the first v2(a−1) passes of its excursion are safe

The pass map is 2-adically 1-Lipschitz and monotone: if every block of one list is the block of another plus a multiple of 2Q (extra blocks on the left multiples of 2Q) and the second list's pass gives a list, so does the first's, with Q in place of 2Q. The first pass from [a, 2a+1], a = 1 + 2mu, is [k, 3k+5, 2k+3], k = 2m−1u, which is φ(blank) plus multiples of 2m−1; so the excursion follows φ of the blank orbit for m passes. For every such a, with no upper bound, the first min(m, 3·260+2) passes never halt and never stop at a block of 1. Kernel only.

next_rel, iter_rel, replay, replay_49153, lean/Replay.lean; replay_3e18_kernel, lean/Replay62.lean

The block count is not bounded by 6 on excursions

From the two-block pass start [a, 2a+1] with a = 2203 + 2221 + 1 (a = 5 mod 12, like every two-block state of the blank orbit) the machine reaches a pass start with 7 blocks after 204 passes, and is back at [a+288, 2(a+288)+1] after 216. The route, in (block count, psi), is exactly the escape the graph allows; the classes to mod 266 missed it because it needs a mod 2222. So the 6-block reduction rests on a statement that fails for some excursions.

seven_blocks, blocks7_204, return7, lean/Seven.lean; py/blockcount.py

The blank orbit cannot step around the 7-block witness

If the blank orbit is ever at [a, 2a+1] with a = a7 − 12j for some j ≤ 200 (a7 = 2203 + 2221 + 1), it walks up to a7 itself, one or two returns at a time, and then reaches a pass start with 7 blocks. Read the other way: if every pass start of the orbit has at most 6 blocks, the orbit goes 1,800 passes in a row near pass 2221.6 without a two-block state [a, 2a+1] at a = 5 mod 12. The 200 steps are checked by the kernel (1,881 passes on 223-bit numbers).

window_seven, six_blocks_long_excursion, window_reach, allOK_W, lean/Window.lean; window in py/blockcount.py

Few large blocks do not exclude a first block of 1

Along the orbit at most 5 blocks are at least ones/32 (computed), the rest a small tail behind a bulk of about [1, 3.4, 3.3, 1]. Lists of that shape still reach a first block of 1: [31, 254304, 870464, 844832, 256088, 32930, 8427] (and one from 255) keep ψ = −57, 4 | ones and every block after the first at least 2, have at most 5 blocks of at least ones/32 at every pass start, and halve their first block down to 1, where the next pass stops. So a bound on the number of large blocks, with ψ, does not rule out the event; what these lists lack is a large first block (1.4·10−5 of the ones, where the orbit keeps it above 0.7%).

lean/Large.lean (wL_one, wL_large, wLb_one, wLb_large); py/largeblocks.py; notes/LAB_NOTES.md, 1 November

A large first block does not bound the halvings

At every change of the first block after pass 50 the orbit leaves it at least 7.6% of the ones, and the runs between changes have at most 5 front stops (108 passes, computed). But a large first block does not stop the halving: [255, 512, 32, 60, 32, 64, 9] (ψ = −23, first block 26% of the ones) and [255, 528, 48, 24, 8, 32, 64, 128, 129] (ψ = 1, 21%) keep 4 | ones and every block after the first at least 2, halve their first block 255 down to 1 with no other change, and then stop at a block of 1. An exact search finds such lists, first block at least 1/5 of the ones and |ψ| ≤ 21, for every run length tried (4 to 8 halvings, computed). So the first block's share of the ones, with ψ, does not exclude the event at these sizes; whether the share must shrink for very long runs is open, and a count of parity bits suggests it need not (heuristic).

lean/BigFront.lean (wF_one, wF_firsts, wH_one, wH_firsts); py/bigfront.py; notes/LAB_NOTES.md, 1 November

native Proved in Lean with native_decide

No halt in the first 10,000,000 steps

The same run for 107 steps, evaluated by compiled code.

blank_runs_10M, lean/Blank.lean

The return map below 262, in seconds

The same explore run on the whole class in one native_decide, so the regular check covers it too: returns_2_62 and no_one_3e18 trust Lean's compiler for this one evaluation. Everything that says what explore means is the kernel's.

returns_2_62, no_one_3e18, lean/Return.lean

trusted Computed, not proved

No halt in the first 1011 steps

The shared C simulator runs 1011 steps from blank tape without a halt (15,234 ones at the end; 3,641 at 109 steps). It agrees with the Python reference simulator on the first 80 records of the run (a test).

tools/c/tmrun.c, tests/test_machine.py

The closed form matches every pass of the first 109 steps

Every time the head is in A on a new cell at the right end in the first 109 steps (1,005 times), the tape is blocks of ones separated by single 0s, and the block lists are exactly the orbit of the closed form from [2, 2]. Pass n starts with 4(n+1) ones. The test checks the first 108 steps.

py/passmap.py, tests/test_machine.py (test_orbit_against_c)

No simple conserved quantity

No a·ones + b·pos + W[state] is conserved modulo 2 to 12. The count of ones is 0 mod 4 at pass starts, but not between them.

tools/py/bbtools/invariants.py

The Lean pass map is the closed form of py/passmap.py

The Lean definition next gives the same result as passmap.py on 3,000 random block lists and on the halting and stop-block-1 examples, and its orbit is the Python orbit for the first 400 passes; the Python form in turn matches every pass start of the first 109 steps of the machine. The Lean theorems are about next itself, so this only ties the two write-ups together.

tests/test_machine.py (TestLeanPassMap)

The return map G(a) = a + 12k, for every a below 274

Run on residue classes a = p + q·u (parities known while q is even, classes split otherwise) down to a mod 274: 82,363 routes from [a, 2a+1] back to [a+12k, 2(a+12k)+1] after 9k passes, k = 1 to 11; no class halts or meets a stop block of 1; only a = 1 is set aside (it stops at a block of 1). The members below 274 of the 15,828 classes still open were run one by one and return too (k = 9 to 12). So for every a = 1 mod 4 with 5 ≤ a < 274 the excursion is safe. 2.5 minutes (mod 262: 24 seconds).

python3 py/returnmap.py classes 72, runs/classes72.txt

No halt in the first 1.4·1022 passes

The orbit is [5, 11] at pass 3, and the states [a, 2a+1] follow each other by G with a = 5 mod 12 (checked against the orbit for 30,000 passes). With the line above, the orbit of the pass map has no halt and no stop block of 1 until a reaches 274, about pass 1.4·1022 (pass n has 3a + 1 = 4(n+1) ones), and by halts_only_by_one the machine does not halt before. Rests on the Lean pass map and on the Python computation, whose passmap is tested against Lean's next.

python3 py/returnmap.py orbit 200000, notes/LAB_NOTES.md

The first 1011 passes, one at a time

The pass map iterated in C from [2, 2] for 1011 passes (35 CPU minutes), with no residue classes: no halt and no stop block of 1, a plain check of the start of the line above. After pass 50 no sweep stops at a block below 59, or below 1.4% of the ones on the tape; 2 to 6 blocks; two-block states [a, 2a+d] with |d| ≤ 3 except 5,298 times. The C program agrees with py/passmap.py at every checkpoint (list and hash of the whole run) up to 107 passes.

c/passorbit.c, runs/orbit_1e11.txt, py/passorbit.py, tests/test_passorbit.py

The first block along the first 108 passes

Iterated in Python on the closed form: every list keeps blocks after the first at least 2 and no two passes in a row stop at the first block, as proved. The first block falls only at stops at the first or second block; over 108 passes a descent (a stretch over which it never grows) contains at most 5 halvings and loses at most a factor 32 (12,024,895 to 375,777 near pass 1.3·107), and after pass 50 the first block stays above 0.7% of the ones. The event needs it to fall to 1: about 18 more halvings in one descent even from its lowest point.

python3 py/front.py stats 100000000, tests/test_front.py

The orbit of G is a counter

G never goes down: the state [a', 2a'+1] has 3a'+1 ones, four more per pass than [a, 2a+1] (next_sum), so a' = a + 12k with k ≥ 1. From a = 5 the orbit steps through the values a = 5 mod 12 in order and skips exactly those inside a jump, a + 12j with 0 < j < k(a): 4.8% of them in the first 300,000 returns (up to a = 3,780,401), where k = 1, 2, 3, 4 occur 285,232, 14,510, 251 and 7 times. The deep values are on it: every a = 2r + 1 with r even in that range, and the values with v2(a−1) = r occur about 2−r as often as for a uniform a. So there is no orbit to follow: in practice the machine halts if and only if some excursion from [a, 2a+1] is unsafe.

python3 py/dynamics.py orbit 300000, runs/dyn_orbit.txt, tests/test_dynamics.py

An excursion reads only the low bits of a

The route of the excursion from [a, 2a+1], and so k and the stop blocks as fractions of a, depends only on a mod 2m for some m: for random a of 64 or of 1,024 bits, m is 5 on average and at most 16, and k and the margin have the same distribution at both sizes. The classes that need more than m bits have measure about 2−0.81m (15,828·2−72 of a = 1 mod 4 at m = 74).

python3 py/dynamics.py random 1024 1000, python3 py/dynamics.py tree 72

No induction on block sizes alone, even from the excursion's own shape

With the constants of the closed form dropped and every parity chosen freely (all that a statement made only of inequalities between blocks can see), the lists reachable from [1, 2], the shape [a, 2a+1] divided by a, have smallest first block 1/6, 1/12, 1/24, 1/48, 1/48, 1/96, … of the ones after 1, 2, 3, … passes: it halves every two passes. So an inductive lower bound on the first block or the stop blocks has to say which parities occur. Near a = 1 (a = 1 + 2mu) the excursion agrees, modulo a power of 2 that loses one bit per pass, with the orbit of the closed form from [1, 3], whose last block is a fixed 3 feeding an inner counter [x, 2x+6, 3]: the deepest routes are orbits of the same map one level down, so the induction would have to be self-similar.

python3 py/induction.py free 12, py/induction.py sentinel, tests/test_induction.py, notes/LAB_NOTES.md (1 November)

The excursion of a = 1 + 2mu runs the blank orbit

A last block that is 3 modulo 2r acts as a sentinel for about r passes. The first pass from [a, 2a+1], a = 1 + 2mu, is φ(blank) modulo 2m−1, and pass t+1 is φ(orbit t) modulo 2m−t−1 for t = 0 … m−2, with the blank orbit's route and every block at least the blank orbit's (checked for m = 12 and 64 with 2,000 values of u each, m = 3,000 with 30, m = 3·104 with 3). So for every a the first v2(a−1)−1 passes of its excursion replay the blank orbit and cannot meet a stop block of 1 unless the blank orbit does; the first block stays above a/4 meanwhile. This is why the open set of the return map accumulates at a = 1. After the sentinel runs out, the deep excursions replay values of the blank orbit's counter in further phases, but the transitions, where the high bits of a enter, have no closed form (observed).

python3 py/sentinel.py deep 30000 3, runs/sentinel_deep_3e4.txt, tests/test_sentinel.py, notes/LAB_NOTES.md (4 November)

A second invariant: psi

psi = yk − 2yk−1 + 4yk−2 − … obeys 2·psi(next) = −psi + 3(−2)n − 7 exactly, where n is the number of blocks the sweep crosses past the last. On [a, 2a+d] it is d, so the six d-chains of the return map are this recurrence. The last block's parity is psi mod 2. It ends the halving loop of [110, 63, 23]: that loop maps psi to (psi − 13)/4 and needs psi = 1 mod 4 every round, so it runs about log4|psi| rounds. The free-parity game, which drives the first block to 0, ignores it.

psi_step, psi_symbolic in py/invsearch.py (sympy identity for k ≤ 12; brute force in tests/test_invsearch.py); kernel proof: psi_next, lean/Psi.lean

psi and the block count on the orbit

Over passes 31 to 108 of the blank orbit, (block count, psi, stop index) takes 65 values, and over every excursion class a = 1 mod 4 down to mod 266 it takes 82: never more than 6 blocks, psi between −21 and 24.

runs/psi_triples_orbit.txt, runs/psi_triples_classes.txt, py/invsearch.py

A conditional reduction to the block count

The (block count, psi) graph, with every stop index psi allows and no two front stops in a row, is exact for every list. With at most 6 blocks it has 158 states, and on its paths at most 9 front stops come between two other changes of the first block. A front stop halves the first block, so with at most 6 blocks a first block of 1 needs one of those changes to leave it at most 511.

parity_graph, run_bound in py/invsearch.py; notes/LAB_NOTES.md, 1 November

heuristic Evidence only

Stop blocks stay above a fixed fraction of a

On every route down to mod 274, each stop block is at least about a/64 (2−6 from depth 48 to 74, 2−4 from 19 to 45): the worst fraction shrinks with the depth m of the residue class, about as 2−m/10 or slower (a = 2r + 1: about a·2−r/10). A stop block of 1 would need it to shrink like 2−m. The route list is infinite: the tail left by the first pass lives v2(a−1) passes, so k is unbounded, and the front runs nested excursions inside it; for each k the routes are finite (k = 1 to 5 need a mod 28, 217, 226, 235, 244).

python3 py/returnmap.py classes 72, notes/LAB_NOTES.md

Collatz-like mixing, but only on a thin set

The classes still open at depth D (members whose route needs more than D+2 bits) number 5, 20, 67, 261, 584, 2,061, 4,332, 15,828 at D = 16, 24, …, 72: about 20.19D, a 2-adic Cantor set of dimension about 0.19 that holds every a not yet proved safe (and a = 1, whose excursion is the stop block of 1). On it the blocks are a·c + e with c a dyadic fraction whose odd numerator is about as long as the modulus (51 bits at depth 48), and no two open classes share their coefficients even up to scale (584 of 584 at depth 48): the deep excursions mix the bits of a like an affine map with odd multipliers, as Collatz does, and are not a finite automaton in these coordinates. What separates this from Collatz is the margin: a halt needs a stop block of 1, a fraction about 1/a, and every route checked keeps it above 1/64.

python3 py/dynamics.py tree 72, python3 py/dynamics.py mixing 48, notes/LAB_NOTES.md

Which starts meet a stop block of 1

The pass map from other starts. Of all 268 million lists of 1 to 28 ones, every one with an odd count meets a stop block of 1 or halts, and every such event comes by pass 59; the survivors of 60 passes survive 1,000. Every two-block start [a, b] with a ≥ 2, a, b ≤ 104 and 4 | a+b (the blank orbit's class) runs 1,000 passes without the event, and 5·106 random lists with an even count and blocks near 109 never meet it. The event needs a sweep to stop at a block of 3 in the first two places one pass earlier: [x, 3, z] with x ≡ 2, z ≡ 3 mod 4 meets it on its second pass, and on the machine itself such lists halt a few passes later. So the event belongs to small blocks, and the blank orbit's stop blocks grow with the tape.

c/passorbit.c, runs/, notes/LAB_NOTES.md (31 October, the wider search)

No invariant of sizes or fixed residues

Small starts reach the stop block of 1 by a halving loop: a stop at the first of three blocks, then an even last block on four, repeated, halves the first block every two passes ([110, 63, 23] reaches it in 9 passes, every block but the last at least 23). So no lower bound on block sizes is kept by the pass map, and since each pass halves blocks, the route depends on ever higher bits: no set described by inequalities and residues modulo a fixed power of 2 is closed under the map and excludes the event. What keeps the orbit out of the loop is the 2-adic digits of its blocks.

python3 py/front.py loop, notes/LAB_NOTES.md

The first block on the bounded graph

Constants dropped, the shapes of lists moved along every path of the 6-block graph keep the first block above about 1.1·10−5 of the ones (0.0024 with 5 blocks, 0.083 with 4). This is a converged game on a grid, not a certificate. With a bound on the block count and a certified version of it, the event would be ruled out.

shape_game in py/invsearch.py

So the blank orbit is expected to reach 7 blocks

Along 106 returns of the blank orbit (a up to 1.26·107) excursions last at most 36 passes and every a = 5 mod 12 with v2(a−1) ≥ 4 is visited; only values with v2(a−1) = 2 or 3 are skipped. The witness has v2(a7−1) = 203, and the jumps grow only slowly with v2 (k = 24 at 203). So unless some excursion below 2222 lasts 1,800 passes, about ten times the longest expected, the blank orbit does not stay at 6 blocks: it has 7 at about pass 2221.6. That step rests on the observed jump sizes, not on a proof.

visits, window in py/blockcount.py; tests/test_blockcount.py; notes/LAB_NOTES.md, 1 November

open Open

Any bound on the block count

No fixed cap K is expected to hold. The sentinel orbit from [1, 3], which deep excursions a = 1 + 2mu follow for about m passes, has its first 3, 4, 5, 6 and 7 blocks at passes 2, 4, 8, 202 and 269,206, and the nesting of its own excursions suggests the count keeps growing, slowly, with the depth (heuristic). With the window argument, every cap the sentinel orbit breaks would also be broken by the blank orbit.

passorbit loose in c/passorbit.c; notes/LAB_NOTES.md, 1 November

An induction for the excursion

The excursion from [a, 2a+1] for every a (the orbit of G is a counter, so a statement for all a is what is needed). The route list is infinite because of the halving tail and the loops it nests, and the deep routes mix the bits of a, so a finite table or automaton will not do: this needs an inequality proved by induction on the tail length, that stop blocks stay above a fraction of a that shrinks slower than 1/a (observed: a/64 on every route to mod 274). With orbit_ok_upto (Lean: if every a below B returns, the first (3B+4)/4 passes are safe) and the reduction, that would prove the machine never halts; Lean's kernel now covers a < 262, and for every a it confines a failure to 67 residues mod 234. A first attempt (1 November) found no such induction: bounds on sizes alone are not kept (free parities halve the first block every two passes), so the statement must carry parities, and the deep routes reproduce the problem one level down. Equivalently (halts_only_at_front), a lower bound above 1 on the first block along the orbit. Since 4 November the self-similarity is exact (next_phi): the deep routes replay the blank orbit itself, so an induction on a could use the orbit's own earlier passes; what it lacks is the congruence for every m as a theorem and a closed form for the transitions between phases. On 5 November the first phase became a theorem for every a (replay): what remains is a reference orbit for each later phase, to which next_rel could be applied in the same way.

notes/LAB_NOTES.md

Does it halt from blank tape?

Not known.

Check it yourself

bash scripts/setup-lean.sh                    # Lean 4.34.0, core only
. /etc/profile.d/lean.sh
bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/lean/check.sh   # the library, then Machine, Rules, Blank, Pass, Front, Seven, Window, Return, Thin, Visit, Psi, Plan, Run7, Large, BigFront, Axioms (about 2 minutes)
JOBS=4 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/lean/check_return62.sh   # the return map below 2^62, kernel only (17 minutes with 4 jobs, under 2 GB each)
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/tests/test_machine.py
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/tests/test_passorbit.py
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/py/passmap.py orbit 40
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/py/passmap.py check 3000 6
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/tests/test_returnmap.py
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/tests/test_front.py
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/tests/test_induction.py
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/py/induction.py free 12   # 5 s
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/tests/test_invsearch.py
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/tests/test_blockcount.py
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/tests/test_largeblocks.py
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/tests/test_bigfront.py
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/py/returnmap.py classes 72   # 2.5 min
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/tests/test_dynamics.py
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/py/dynamics.py orbit 300000
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/py/dynamics.py tree 72        # 4 min
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/tests/test_sentinel.py
python3 bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/py/sentinel.py deep 30000 3   # about 1 min
gcc -O2 -o tmrun tools/c/tmrun.c && ./tmrun 1RB1RA_1RC1LB_1LD0RA_1LB0LE_1LF1LD_---0LD 100000000000