Busy Beaver Explorer / holdouts / 1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA / explained

A 6-state Busy Beaver machine · Status as of 13 November 2026.

Does this machine ever halt?

1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA

Decided: it never haltsProved in this repository, checked by Lean and by Coq. The ledger below says what each part rests on.

It never halts, and Lean proves it. Two blocks of the tape trade places, about seven times longer each round; now and then the left block is poured into a third block at the far right. After 1.8·1015 steps the whole pattern repeats exactly, with only that third block longer each time.

native_decideno haltLean theorem nonhalt; two replays and twelve rules evaluated by compiled code.
KernelexecutorThe symbolic executor that does the replays is proved sound in Lean.
ComputedcycleFrom step 1.8·1015 the run repeats every 116,320,154 visits of the left end, the right block 321,042,928 words longer (the counts are computed, the return is proved).
Kernelcycle ⇒ no haltThe last step of the argument, proved in Lean.
Computed17 / 17Injected defects reported by the cycle checker.
Heuristicsqrt/sqrtThe growth shape of the two sides of the tape (see below).
Also proved in CoqA second proof assistant checks the same result: H65826.nonhalt : ~ halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/coq. Coq 8.18 compiles it and Print Assumptions reports no axioms; the build log is next to the files. A shorter proof of the same theorem (the same symbolic executor and runs in one self-contained file of 1,616 lines; Coq 8.20.1 checks it in about 49 seconds) is on a branch of our fork of busycoq, ready to be proposed upstream: bb6-nonhalt-1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_HHH1LA.
Community labelIn the community's BB(6) tracker the machine's class is Unknown. These are labels read off the run by others, not results.
Kernel proved in Lean, checked by the kernel only
native_decide proved in Lean, one evaluation trusts the compiler
Computed C or Python in the repository, tested but not proved
Heuristic evidence and estimates
Open not known
The machine

6 states, two symbols, 1 halting transition

Each entry says what to write, which way to move and which state to enter. The machine starts in A on a blank tape (all 0s).

The machine stops when it is in F reading 0. F is entered only from D1 (writes 0, moves L): 0 D>1. So a halt is the moment this pattern appears, with the head on the cell after >.

statereads 0reads 1
A1 R B0 R C
B0 R C1 R C
C0 L D0 R A
D1 L E0 L F
E0 L A1 L C
Fhalt1 L A
One circle per state. A solid arrow is taken on reading 0, a dashed one on reading 1; its label is read:write move. Red marks a halting transition. Hover a state or a row to single out its arrows.
Follows the simulator below. The orange state is the current one and the thick arrow is the transition about to fire. The bars count how often each transition has fired since step 0, so the rare ones stand out.
Watch it run

The tape from blank, step by step

This is the real machine, simulated in your browser. Step it, play it, or jump to a step count. Below the cells is the whole visited tape in the notation of the notes: 1^5 is five 1s, and C>0 is the head in state C on a 0.

Jump to:
step 0state Acells visited 1ones 0
Cells around the head (dark = 1, dashed = never visited).
The same tape, grouped into repeated words: (10)7 is the word 10 seven times in a row, and the orange tag is the head. The grouping is found afresh at every step by looking for the longest repeat of a word of up to 8 cells, so it shows the counts a machine keeps on its tape without anyone having to decode them first; it is a display, not a result.
The run at a glance

Space-time diagram and records

The diagram stacks the tape at many moments. Sampling at each new cell shows the shape of the run as the visited region grows; sampling evenly in time shows where the head spends its time. The records list every step at which the head reaches a cell no earlier step reached, with the side, the width so far and the whole tape: the first place to look for a repeating macro structure. Click a row of the diagram to send the simulator above to that step.

Four levels

From six states to one number

The question "does this machine halt?" can be asked at four levels of description. Each level keeps less detail than the one above it, and each step down is a theorem saying that the answer is the same. The page walks down the ladder: the six-state machine on its tape; the tape read as blocks of repeated words at the moments state E reaches the left end; whole cycles of the long phases, each a rule that holds for every size of the blocks; and finally one number r, the length of the last block, which grows by 321,042,928 every period and never leads to a halt.

One moment, four descriptions

Pick an event. The browser runs the real machine from blank tape up to that moment and reads its tape. The rows show the same instant at each level: the cells, the blocks of words, the cycle rule of the Lean proof whose template the tape fits (if any), and where the moment sits on the way to the growth cycle. Where a rule fits, the browser also runs the machine on to the end of the rule's cycle and checks that it arrives exactly where the rule says.

event 440 of the run
Jump to:
1 · Machine
seven-cell words 1011001three-cell words (011, 101, 110) and trains of themother cellsdark = 1, pale = 0; the triangle is the head, state E
2 · Blocks
3 · Cycle rule
4 · Growth cycle
The step counts are exact: the browser counts every step from blank tape. Event 2,600 is about 1.4·108 steps in; the first jump that far takes a second.
Level 1 · First look

The shape of the run

Left of the start, the visited part of the tape grows like the square root of the step count, the signature of a head sweeping back and forth across the whole tape and adding a cell or a few at the end of each sweep (a bouncer-like shape) (fitted exponent 0.498). Right of the start it grows like the square root of the step count, the signature of a head sweeping back and forth across the whole tape and adding a cell or a few at the end of each sweep (a bouncer-like shape) (fitted exponent 0.478).

2^42^82^122^162^202^242^282^02^42^82^12■ left of start ■ right of start (steps across, cells up)

After 109 steps the tape spans 43,491 cells (12,594 left of the start, 17,410 right), with a density of 1s of 0.609.

The tape (run-length coded, 1^5 is five 1s, C>0 the head in state C on a 0) at some of the last moments the head reached a new cell, cut to 400 characters:

sidesteptape
left955,905,721E>0 1 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0
left971,976,277E>0 1 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0
left987,704,249E>0 1 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0
right956,685,8051 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1
right972,322,6231 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1
right988,040,9011 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1^2 0 1^2 0^2 1

These are measurements of one bounded run, sorted by tools/py/bbtools/triage.py; the macro structure behind them is the next thing to find.

Level 1 to level 2

Seven-cell words on the left, three-cell words on the right

Look at the tape each time the head, in state E, reaches the left end of the visited tape: an event. The tape is then a block of seven-cell words 1011001, a short irregular zone, and then blocks of the three-cell word 011 separated by a few zeros. The last block, (011)^r, ends the tape.

Going right, the head shifts a block of three-cell words by one cell (3 steps a word). Going left, it crosses two words at a time (18 steps). So what happens at the end of a block depends only on whether its length is even or odd: every cycle rule the proof needed has the form "for all lengths of this parity".

The Lean proof works at this level with a symbolic executor: a program whose tape is a list of cells and blocks (w)^n, where n may be c + a x with x unknown. One move of the executor either crosses a whole block with a shift rule, or makes one ordinary step (opening a block only when its count is surely at least 1). A shift rule says: in state q, with the word u just behind the head, the head crosses k copies of a word w and leaves the word v behind it, in s steps, without looking at anything else. Each of the 31 shift rules is a Lean statement about the machine for every tape around those cells, checked by the kernel (shRTbl_ok, shLTbl_ok in lean/ExecData.lean), and the soundness theorem run_sound (lean/Exec.lean, kernel) says that whatever the executor does in some number of moves, the machine does, for every value of the unknowns. That is the theorem that makes level 2 answer the same as level 1.

The browser writes u, then n crossings' worth of copies of w, between twelve random cells on each side, puts the head in state q where the rule says, and runs the real machine for n·s steps. The rule holds if the head never reads a random cell, ends in state q at the far side, and the cells read u vn as the rule says. Words are written nearest cell first, as in the Lean file, so on the left of the head they appear reversed.
Level 2 to level 3

Collect, expand, drain

Three regular phases take almost all the time. p counts the seven-cell words, q or m the three-cell words of the middle block, r those of the last block.

phasetape when state E reaches the left endone cycle
collect0 (1011001)^p (101)^5 10 (011)^q 000 (011)^r, q even, r odd2 events: p + 2, q − 2
expand0 (1011001)^p 1011 0^5 110110011010 (101)^m 1000 (011)^r, m even, r odd4 events: p − 2, m + 14
drain0 (1011001)^p 1011 0^5 1101100110110 (011)^16 001101100110 (011)^r, r odd72 events: p − 52, r + 414

Collecting turns three-cell words into seven-cell words one for one; expanding gives seven three-cell words back for each seven-cell word. So each round the blocks are about seven times longer: about 600, 4,370, 30,750, 215,000, 1,506,000 words. Between the phases there are short irregular stretches where the separators collide, and trains of cars (011)^4 0 are built and taken apart. Usually the next round starts. Sometimes the stretch ends in the drain pattern: then the whole left block is poured into the last block (414 words of three for 52 words of seven), and the left part starts again from a small state, in front of a much longer last block.

At level 3 a whole cycle of a phase is one statement. A cycle rule is a template of the whole tape whose counts are b + 2x before and b' + 2x after, one x for each block that changes. It is proved for all values of the x by one run of the executor itself, without cycle rules, from the template before to the template after (ruleOK_of_run, kernel; the run is evaluated by native_decide: rule0_ok … rule11_ok in lean/ExecData.lean). The executor then applies a rule N times in one move, N as large as the shrinking counts allow; the induction over N is in Lean (rule_instN, kernel), so the choice of N is not trusted. Twelve rules were enough: eleven are collect or expand, plain or with inert trains in between, and one, rule 8, is the drain. Separately, lean/Phases.lean proves the plain collect and expand cycles by hand for any number of cycles, with the kernel only (collect2, collect_n, expand4, expand_n); the replay does not need them.

Every block that has a variable gets the same x here. The browser writes the template on a blank tape, puts the head on its first cell in state E, runs the real machine until state E has reached the left end the rule's number of times, and compares the tape with the template after. The drain (rule 8) takes about five million steps. lean/Phases.lean writes the blocks of three-cell words with the six-cell word 110110 and allows any count b + x, not only b + 2x.

The same rules can be looked for in the run itself. The scan below runs the machine from blank tape through its first 2,600 events, tests every event against the 14 templates, and wherever one fits checks the rule's prediction against the event that many events later.

Level 3 to level 4

The left part comes back to the same state

The left part of the tape never needs more of the last block than the parity of its length, and a drain adds an even number of words. After the second drain the left part reaches a state that it meets again, exactly, two drains later:

C(r) = E> 0 (1011001)^59 1011 00000 1101100110110 (011)^16 001101100110 (011)^r

eventstepwhat happens
2,260,3296.7·1013first drain: p 1,505,827 → 115, r 4,001 → 11,991,785
5,251,3951.07·1015second drain: p 603,155 → 111, r → 16,797,295
6,086,4511,818,198,163,340,705C(16,797,709), the first time
59,675,3525.4·1016drain after 11 phases: p 35,724,983 → 99, r → 301,226,589
116,039,6456.0·1017drain after 10 phases: p 4,598,419 → 111, r → 337,840,223
122,406,605725,814,446,706,290,623C(337,840,637) = C(16,797,709 + 321,042,928)

Events and steps computed by the simulators (py/closure/accel.py, py/replay/engine.py, verify/sim3.cpp, which agree); the Lean statement does not count them.

One period is two epochs, two drains. To prove that it goes on for ever, one period is run with r replaced by 65 + 2x, x unknown. Whenever a step would depend on the value of x the executor stops; it never had to. It ends in the same configuration with 65 + 321,042,928 + 2x, after 5,581,714 moves (period_run, lean/Period.lean, evaluated by native_decide). With run_pos this is the theorem grow_cyc: for every x, C(65 + 2x) reaches C(65 + 2(x + 160,521,464)) in at least one step. The run from blank tape reaches C(16,797,709) = C(65 + 2·8,398,822) (reach_cyc: 5,037,044 moves, lean/Arrive.lean). And the kernel proves the last step, nonhalting_of_growth_cycle in lean/Cycle.lean: if the run reaches some C(65 + 2x) and every C(65 + 2x) reaches a later one in at least one step, then the run from blank tape is at such a configuration at later and later steps, so it is still running at every step: the machine never halts.

Why only the parity of r matters

The claim behind the symbolic period can be watched on the real machine for small r: start from C(r) for two odd values of r and compare the two runs event by event. Up to the last block the two tapes are the same, and the last blocks keep their difference. Start one of them from an even r and the tapes part at once; C(r) with r even halts, at event 21,362,421 (computed, py/closure/classes.py).

The left part is the tape from the head to the start of the last block (011)^r; the plot shows its length (in cells) and the last block's count, event by event, for the first r. 3,000 events are about 1.5·108 steps for each run.
Level 4 · Try it

Apply the growth cycle yourself

Once the left part of the tape has reached its recurring state, the run is one rule repeated: the last block gains 321,042,928 words and everything left of it comes back exactly. Press the button to follow the orbit on the number r alone.

A narrow escape

Almost the same tape halts

The same node with other counts is not safe. With 61 words instead of 59 in the left block,

E> 0 (1011001)^61 1011 0^5 1101100110110 (011)^16 001101100110 (011)^r, r odd ≥ 65,

halts after 1,772,276 + 5,220 (r − 65) steps (computed by py/closure/classes.py, confirmed by plain simulation for r = 65, 67, 71). C(r) itself with r even halts too, much later, at event 21,362,421. So there is no simple description of "safe tapes" that contains the run: it is safe because it sits on one exact orbit. That is why the automatic deciders, which look for such descriptions, left this machine open, and why the proof follows the orbit itself.

The browser can run the halting neighbour: pick r and the number of seven-cell words, and the real machine runs from that tape.

With 59 words the browser stops after 2·107 steps; that the run from C(r) never halts for odd r ≥ 65 is the Lean theorem grow_cyc, not something a bounded run can show.
The bottom line

It never halts

It never halts.

Started on a blank tape, 1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA runs for ever. From step 1,818,198,163,340,705 on its run is the growth cycle: C(r) comes back as C(r + 321,042,928) after 116,320,154 arrivals of state E at the left end, and so on without end.

The Lean theorem is nonhalt : ¬ HaltsFromBlank in lean/Replay.lean, ledger level native_decide. What it rests on, exactly:

  • The Lean kernel checks the definitions of the machine, the soundness of the symbolic executor (run_sound, run_pos, rule_instN, ruleOK_of_run in lean/Exec.lean), the 31 shift rules (lean/ExecData.lean, each by rfl) and the last implication, nonhalting_of_growth_cycle (lean/Cycle.lean).
  • Fourteen evaluations by native_decide, which trust Lean's compiler as well as its kernel: the twelve cycle rules (rule0_ok … rule11_ok, from 422 to 201,007 executor moves each), the arrival from blank tape (arrive_run, 5,037,044 moves) and the period (period_run, 5,581,714 moves). #print axioms nonhalt lists propext, Quot.sound and these fourteen evaluations; there is no sorry.
  • Not used: any simulator outside Lean. The executor's strategy (which rule, how many times, how to re-bracket the tape) is not trusted; only its soundness is, and that is proved.
  • Not stated in Lean: the numbers of steps and events, such as the step 1,818,198,163,340,705 at which C(16,797,709) is first reached; Lean says only "reaches, in at least one step". Those counts come from py/closure/accel.py, py/replay/engine.py and verify/sim3.cpp, which agree (computed, not proved).

The short cycle rules can be checked by the kernel alone (decide +kernel was tried on rule 4, 422 moves, and rule 11, 3,255 moves); the drain rule and the two long runs have not been, so there is no kernel-only proof of nonhalt yet. A second proof of the same statement, in Coq on top of busycoq (coq/H65826.v, nonhalt : ~ halts tm c0), evaluates all its runs inside Coq's kernel with vm_compute and reports no axioms; the ledger lists it as kernel level.

What is known

Every result, by what it rests on

Status as of 13 November 2026. The same list as the proof-status page, built from the same file.

Kernel
step_none_iff, lean/Blank.lean
The halting configurations

The machine stops exactly when it reads the symbol of a halting transition (F0); the generated statement covers every configuration.

Kernel
blank_runs_kernel, lean/Blank.lean
No halt in the first 10,000 steps

The list simulator of the shared library, proved to agree with the machine's semantics, runs 10,000 steps from blank tape without a halt, evaluated by Lean's kernel.

native_decide
blank_runs_native, lean/Blank.lean
No halt in the first 107 steps

The same run, evaluated by compiled code.

Computed
holdouts/triage.json
No halt in the first 109 steps

The C simulator tools/c/triage.c runs 109 steps without a halt; at the end 43,491 cells have been visited and 26,502 of them hold a 1.

Heuristic
tools/py/bbtools/triage.py
Growth shape: sqrt/sqrt

Left of the start, the visited part of the tape grows like the square root of the step count, the signature of a head sweeping back and forth across the whole tape and adding a cell or a few at the end of each sweep (a bouncer-like shape) (fitted exponent 0.498). Right of the start it grows like the square root of the step count, the signature of a head sweeping back and forth across the whole tape and adding a cell or a few at the end of each sweep (a bouncer-like shape) (fitted exponent 0.478).

Kernel
a_right, d_left, a_right3 in lean/Rules.lean
Sweeps over the long blocks

L A>(0011011)^n R → L (1100110)^n A> R (13n steps), L (1011001)^n D>1 R → L D>1 (0110110)^n R (23n steps), L A>(011)^n R → L (110)^n A> R (3n steps), for every n, L, R.

Kernel
collect2, collect_n, expand4, expand_n in lean/Phases.lean; collect_raw, expand_raw in lean/Rules.lean
The two long phases, any number of cycles

Collecting: E> 0 (1011001)^p (101)^5 10 (011)^q 000 (011)^r (q even, r odd) becomes the same with p + 2n, q − 2n. Expanding: E> 0 (1011001)^p 1011 0^5 110110011010 (101)^m 1000 (011)^r (m even, r odd) becomes the same with p − 2n, m + 14n. One cycle each with its exact step count (48a + 48b + 72p + 476 and 240b + 240c + 144p + 2812), n cycles by induction.

native_decide
nonhalt, lean/Replay.lean
The machine does not halt

From blank tape the machine never reaches a halting configuration: nonhalt : ¬ HaltsFromBlank. It combines the three claims below with nonhalting_of_growth_cycle. Axioms used: propext, Quot.sound and 14 compiled evaluations (native_decide): the two replays and the twelve cycle rules.

Kernel
coq/H65826.v, coq/SymExecN.v; build: sh coq/build_H65826.sh /path/to/busycoq
The machine does not halt: a second proof, in Coq (busycoq)

The same argument, ported to Coq on top of busycoq's definitions: nonhalt : ~ halts tm c0. The symbolic executor is proved sound against busycoq's step, and all runs are evaluated inside Coq's kernel by vm_compute; Print Assumptions nonhalt reports no axioms. Clean build with Coq 8.18.0: about 40 s.

Kernel
nonhalting_of_growth_cycle, lean/Cycle.lean
A growth cycle implies non-halting

With C(r) = E> 0 (1011001)^59 1011 00000 1101100110110 (011)^16 001101100110 (011)^r: if the run from blank tape reaches some C(65 + 2x), and every C(65 + 2x) reaches C(65 + 2(x + 160,521,464)) in at least one step, the machine does not halt from blank tape. The two hypotheses are proved by the replay below.

Kernel
run_sound, run_pos, rule_instN, ruleOK_of_run in lean/Exec.lean; shRTbl_ok, shLTbl_ok in lean/ExecData.lean
A symbolic executor, proved sound

Tapes are lists of cells and blocks (w)^n with n = c + a0x0 + a1x1 + …, the x free. A move is a shift rule from a table (a block crossed at once, one or two copies at a time), or one machine step, and at each arrival of state E at the left end a re-bracketing of the tape and a cycle rule applied N times at once. Any step that would depend on a variable fails. Theorem: if the executor goes from S to S′ in k moves and its tables are valid, the machine goes from S to S′ for every value of the variables. The 31 shift rules are proved by evaluation in the kernel; the N-fold application of a cycle rule by induction.

native_decide
rule0_ok … rule11_ok, lean/ExecData.lean
Twelve cycle rules, for all values of their counts

Each rule says: this tape with counts bi + 2xi comes back with counts bi + Di + 2xi, for all xi (eleven are collect or expand, plain or with inert zones in between, 2 or 4 visits; one is the drain, 72 visits, 201,007 executor moves). Each is one run of the executor without cycle rules, evaluated by native_decide.

native_decide
reach_cyc, lean/Replay.lean; arrive_run, lean/Arrive.lean
Blank tape reaches C(16,797,709)

5,037,044 moves of the executor from blank tape end at C(16,797,709) (arrive_run, native_decide, 13 s); by soundness the machine reaches that configuration.

native_decide
grow_cyc, lean/Replay.lean; period_run, lean/Period.lean
C(65 + 2x) reaches C(65 + 2(x + 160,521,464)), for every x

5,581,714 moves of the executor from C(65 + 2x), x a free variable, end at C(321,042,993 + 2x) (period_run, native_decide, 14 s); by soundness the machine does so for every x, in at least one step.

Computed
py/closure/cycle.py check, mutate, instance; py/replay/gen.py --check
The growth cycle: visit and step counts

C(r) reaches C(r + 321,042,928) after 116,320,154 arrivals at the left end and 650,373,336,347,246,654 + 4,382,930,856 (r − 65) steps. That C(r) reaches C(r + 321,042,928) is a Lean theorem (above); the counts come from two symbolic simulators that agree (py/closure/accel.py and the model of the Lean executor, py/replay/engine.py), checked against numeric runs from C(65), C(67), C(79) and three periods of the real run; 17 injected defects are all reported.

Computed
py/closure/cycle.py reach, py/closure/check_events.py, c/events.c
Blank tape reaches the cycle: step counts

That blank tape reaches C(16,797,709) is a Lean theorem (above). The step counts are computed: the run is at C(16,797,709) after 1,818,198,163,340,705 steps (event 6,086,451), and at C(337,840,637) after 725,814,446,706,290,623 steps. The word-level engine agrees with a plain C simulator at all 24,646 events of the first 1010 steps (step count and CRC of the tape).

Computed
py/closure/classes.py
Neighbouring classes halt

The same pattern with 61 words in the left block halts for every odd r ≥ 65, after 1,772,276 + 5,220 (r − 65) steps (confirmed by plain simulation for r = 65, 67, 71); C(r) with r even ≥ 64 halts at its 21,362,421st event. So the real run is safe only because of the exact orbit it is on.

Computed
verify/README.md, verify/run_all.sh
Independent check of the growth cycle

A second accelerated simulator, written from scratch without reading the first (verify/sim3.cpp, validated against plain simulation to 1010 steps), lands exactly on C(16,797,709) at step 1,818,198,163,340,705 from blank tape, and takes C(r) exactly to C(r + 321,042,928) at the predicted step for r = 65, 67, …, 85 and r = 16,797,709. It also confirms that C(r) halts for the even r tried (the halting transition is one step after the count stated in the notes: that count excludes the halting step). It checks listed values only; “for every odd r” is the Lean theorem grow_cyc.

Check it yourself

Commands

. /etc/profile.d/lean.sh      # after scripts/setup-lean.sh
holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/lean/check.sh      # Machine, Blank, Rules, Phases, Cycle, Exec, ExecData, Arrive, Period, Replay (1 min)
python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/replay/gen.py --check      # the model of the Lean executor: tables, move counts, events and steps as claimed (40 s)
python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/closure/cycle.py check      # the growth cycle from the claim alone (20 s)
python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/closure/cycle.py reach      # blank tape reaches C(16797709) (5 s)
python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/closure/cycle.py instance   # numeric runs from C(65), C(67), C(79) (40 s)
python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/closure/cycle.py mutate     # 17 defects, all reported (6 min)
python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/closure/classes.py          # neighbouring classes (4 min)
gcc -O2 -o events holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/c/events.c && ./events 1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA 10000000000 > ev10.txt && python3 holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/py/closure/check_events.py ev10.txt --plain
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA 1000000000
holdouts/1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA/verify/run_all.sh      # independent simulator: arrival and one period for several r (about 2 min)