Busy Beaver Explorer / holdouts / 1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB / explained
A 6-state Busy Beaver machine · Status as of 9 November 2026.1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB
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. This machine alternates between long stays at its right end and rounds of full sweeps, each phase longer than the last; every way one phase can lead to the next is proved for all sizes, and linear inequalities on the counts show the run always stays where those rules apply. This page runs it in your browser.
H113677.nonhalt : ~ halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in tools/coq/busycoq/H113677. Coq 8.18 compiles it and Print Assumptions reports no axioms; the build log is next to the files.verify/M_1RB0LE_1RCHHH_1RD1RE_1LA0RF_0RC0LA_0LC0RB.v). As of 19 November 2026 it was open: not merged, not reviewed by the maintainer, and not compiled here unless the ledger below says so. It agrees with the proof here.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 B reading 1. B is entered only from A0 (writes 1, moves R): A>0 1; F1 (writes 0, moves R): F>1 1. So a halt is the moment one of these patterns appears, with the head on the cell after >.
| state | reads 0 | reads 1 |
|---|---|---|
| A | 1 R B | 0 L E |
| B | 1 R C | halt |
| C | 1 R D | 1 R E |
| D | 1 L A | 0 R F |
| E | 0 R C | 0 L A |
| F | 0 L C | 0 R B |
read:write move. Red marks a halting transition. Hover a state or a row to single out its arrows.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.
(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 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.
The question "does this machine halt?" is answered here at four levels of description. Each level keeps less
detail than the one above it, and each step down is a Lean theorem, checked by the kernel: what happens at the lower
level is exactly what the machine does. At the bottom, the question is whether a list of linear inequalities on a
few numbers is kept by twenty arithmetic cases, and that is a question omega can settle.
blank_O).
Level 2Forms and rules
O a b c: a few run lengths. One unit is one rule: a turn of a cycle or an exit, a few end visits.lean/Cycle.lean, Phase.lean, Branch.lean, Ends.lean).
Level 3A map on ten forms
mv_* (lean/Closed.lean) chains a cycle iterate and one exit rule.
Level 4The invariant Good
good_step: from a Good form the machine makes at least one step and reaches a Good form (one mv_* case and omega each).
table_from_blank Kernel follows the run from blank tape through 196 moves, to
T2 34158019330534 128092572489511 160237983842729 41908435347077 at step 5.7·1029, and
good_last Kernel checks with decide that this form is Good. From there level 4 takes over (the bottom line).Pick a moment. The browser runs the real machine from blank tape up to it. Separately, it replays the 27 rules on
numbers alone (level 2), and runs the 20-case map (level 3) from O 14 37 11, and evaluates the
inequalities of Good (level 4). The rows show the same instant at each level; the check marks say that
the separate computations agree. The moments are the ends of all the rule turns from step 29,301 up to about
108 steps.
At the top of the ladder is the machine itself: a tape of 0s and 1s, a head, and the table above. Its table has
one missing entry: B reading a 1. That is the only way to halt. Two transitions lead into B: A reading a 0
(writes 1, moves right) and F reading a 1 (writes 0, moves right). So the machine halts exactly when the head reads
A> 0 1 or F> 1 1 (Lean: halt_A, halt_F in
lean/Rules.lean). Kernel
The proof never looks for these patterns directly. It shows something stronger: from the blank tape, for every
number n, the first n steps are all defined. That is the Lean statement ¬ HaltsFromBlank, where
HaltsFromBlank means "some step reaches a configuration with no transition".
Without the proof, the run gives only bounds: no halt in the first 104 steps (kernel) and
107 steps (native_decide), both in lean/Blank.lean, and none in 109
steps of the C simulator. The simulator above (Watch it run) is this level.
Press Step to see a halt play out on a made-up tape.
Watch the machine for a while and its tape turns out to be made of long runs of a few short words:
1000, 10, a 14-cell word such as 00001000001000, and a few others, with short
fixed pieces between them. So the tape can be written as a form: a pattern with the run lengths as numbers.
That is level 2. For example
is the form O a b c: the head in state A at the left end, then seven 0s, a copies of
1000, b copies of 10, c copies of the 14-cell word, and 101. The proof uses
ten forms. Seven are seen with the head at the left end, in state A or E (the "round-trip" forms, counting
O a 0 c separately), and three with the head at the right end, in state E (the "right-phase"
forms). Pick one to see its shape:
A form names a whole tape, so a sequence of forms with step counts is a description of the run
as faithful as the machine itself, as long as every form is on the tape at exactly the stated step. The first time
the run is in one of these forms is at step 29,301, in the form O 14 37 11. Lean proves this by running
the machine (blank_O in lean/Table.lean). Kernel Try it: the
button runs the machine in your browser and compares the tape with the form, cell for cell. In the picture below
each cell is a thin bar (dark = 1), and the coloured band under it shows which run of the form it belongs to.
Level 2 counts time in rules, and a rule may span millions of steps. What makes that possible is that the head crosses long runs in a simple way, and Lean proves each crossing once for every length:
pass_10_right: C crosses (10)^n to the right in 2n steps and leaves it unchanged.pass_10_left: A crosses (01)^n to the left in 8n steps (it carries 10 along).fill_F: F turns (1000)^n into (1110)^n, 10 steps a copy.fill_B: B turns (0001)^n into (0111)^n, 10 steps a copy.clear_A: A, going left, turns (0111)^n into (0010)^n, 10 steps a copy.Each is proved by running one copy for real (rfl: the kernel computes those few steps) and then a
general lemma: if one copy takes the head through in the same state, n copies do too, in n times the steps
(lean/Rules.lean). Kernel Pick a pass and play it on the real machine with
n = 3.
Using these passes, Lean proves 27 rules. Each rule says: from form X with numbers like (a, b + 6, c + 2),
the machine reaches form Y with numbers that are simple formulas of a, b, c, in an exact number of steps that is
also a formula. The rule holds for every value of the variables. Kernel This is the
theorem that ties level 2 to level 1: a rule is a statement steps N (X …) = some (Y …) about the machine
itself, so a chain of rules is a stretch of the real run, step count included.
The central example is the 4-visit cycle cycle: S1 a (b+2) (c+2) reaches
S1 (a+3) (b+14) c in exactly 80a + 72b + 1356 steps. Each turn uses up two of the 14-cell words (c drops
by 2), and the runs of 1000 and 10 grow by 3 and 12. The head visits the left end four times
on the way.
Each rule's proof is a symbolic run: Lean steps the machine on a tape whose runs have lengths like
b + 2, uses a pass to cross a whole run at once, and at the end shows the tape it got is the target form
(by regrouping, e.g. (0010)^a 0 = 0 (0100)^a). Lean also proves the k-fold repeats such as
cycle_iter, by induction on k. The rules are in lean/Cycle.lean, lean/Phase.lean,
lean/Branch.lean and lean/Ends.lean.
Try any rule: choose small numbers for its variables, and the browser runs the real machine for exactly the stated number of steps. The picture shows the tape over time (rows are moments, time going down; dark = 1) and the path of the head (orange line). The check compares the result with the target form, cell for cell.
Level 3 forgets the turns inside a phase and keeps only the form at the start of each phase. Put the rules
together and every form leads to another form. The graph shows all of them. A loop on a form is a cycle rule, which
runs as long as there are words left to use up. Each arrow out of a form is an exit, chosen by what is left over: how
many 14-cell words remain (c = 0 or 1), how many 0010 remain in T3 (d = 0 to 4), or whether the run just
built has even or odd length. The thicker an arrow, the more often the first 196 moves of the run use it. Click a form
to see its rules and its cases.
lean/Closed.lean):Each case runs one cycle to its end with its k-fold iterate (cycle_iter, cycle2_iter,
cycle3_iter, ucyc_iter, rcyc_iter, gcyc_iter,
g3cyc_iter) and then applies one exit rule. Which exit is decided by a residue: c mod 2 for S1, T2 and
U3, d mod 5 for T3, and the parity of the run being built for RF, RG and RG3. Once the residue is fixed the new
numbers are affine functions of the old ones, so the 20 cases mv_* are exact formulas, proved by
chaining the rules of level 2 (for every value of the variables). Kernel
Not every case is safe for every size. A case needs its numbers to be large enough (for mv_oentry,
b ≥ 6 and c ≥ 2), and some combinations have no case at all, for example T3 running out of 14-cell words while 5 or
more 0010 are left. Those are the gaps the invariant of level 4 closes.
Below, the browser runs the 20-case map alone, on numbers, from O 14 37 11. Next to each move it
shows the case used, whether the new entry satisfies Good (level 4), and whether the map lands on the
same form as the 27 rules of level 2 replayed turn by turn (a separate computation, which also gives the step).
Level 3 needs a starting point. Start from O 14 37 11 at step 29,301 and apply the rules, one after
another, on the numbers alone. A cycle that runs k times is one move, with its steps added up by a formula. After
196 moves the run is at
T2 34158019330534 128092572489511 160237983842729 41908435347077
at step 572,161,236,689,394,206,666,641,378,531 (about 5.7·1029). Lean checks this chain move by move:
each line of table_run (lean/Table.lean) is one rule with its variables filled in, and the
kernel checks the arithmetic. Kernel With blank_O in front it is
table_from_blank: from the blank tape, some run of the machine ends at that T2.
The table lists the 197 states. You can test the first ones against the plain machine: the button runs it from blank tape and checks, at each predicted step, that the tape is exactly the predicted form, cell for cell.
Columns: the step at which the run is in that state, the form and its numbers, the
rule that takes it to the next state (with how many turns, for a cycle), and whether the state is good (level 4). The
plain run was also compared with the first 49 states, up to 3·1010 steps, by a C program
(c/checkpoints.c). Computed That check is separate from Lean. The same replay,
continued by py/macro.py, goes on without a gap to 10300 steps (2,281 states).
The 196 moves cover a finite stretch of the run. To go on forever the proof needs one argument that works for all
later moves. That is level 4, the invariant Good in lean/Closed.lean: for each form, a list
of 3 to 16 linear inequalities on its numbers. They say three kinds of things:
O a b c, b stays between about 1.7 and 4.2 times a, and c between about 0.3 and 2.3 times a, in the
shaded region of the picture below.RF, k is 4 or 5; in RG and
RG3, n is 4 or 5; in T3, 8 ≤ y ≤ 15), and some numbers keep exact relations (in
T3, x = 2a + 4; in U3, x − 2a is between 0 and 2; in RG3, 4y + 21x − 49a is between −63 and 19).O.The picture shows, for the forms O and S1, the region that the ratio inequalities allow (shaded), and the ratios of every O or S1 state of the replay (dots). The ratios move around from phase to phase but stay in the region. Filled dots are good states. Hollow dots are early states, which are still too small for the size condition.
Why do the inequalities keep holding? Each of the 20 cases of level 3 is a fixed affine map on the numbers. So
the step from Good to Good is a question about linear inequalities over the whole numbers,
which Lean's omega procedure decides. Kernel Each case works because:
That is good_step: from a good tape the machine makes at least one step and reaches a good tape. Its
proof has one step_* lemma per form, each split by the residue into its cases, and each case is one
mv_* lemma and one call of omega. The coefficients (up to 1,321) were found by linear
programming on the replay's numbers, with scripts outside the proof. Lean does not trust them: if one were wrong,
omega would fail.
The last state of the replay is good: Lean evaluates its 16 inequalities with decide
(good_last). Kernel Along the replay every entry from the 39th on is good, and
the panel above lets you check any of them, and the case that follows.
The machine 1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB, started on a blank tape, never halts.
Kernel Lean theorem nonhalting : ¬ HaltsFromBlank
in lean/Closed.lean. It rests on Lean's kernel alone: #print axioms for it lists only
propext, Classical.choice and Quot.sound, the three standard axioms of Lean's
logic. There is no native_decide and no compiled code anywhere in the proof.
The argument, in three sentences. From the blank tape the machine reaches a tape that is good: one of ten
forms, with numbers that satisfy that form's inequalities (table_from_blank, good_last).
From any good tape it makes at least one step, without halting, and reaches a good tape again
(good_step). Repeating the second sentence gives runs of every length, and a machine that halts has
runs only up to some fixed length.
A wrong number anywhere, in the replay or the inequalities, cannot make the proof pass. It would only make one of the checks fail.
| Piece | What it says | Checked by |
|---|---|---|
Machine.lean | the machine's table and what a step is (generated from the machine's name) | Kernel |
Rules.lean | the five passes, for any n; the two halting patterns | Kernel |
Cycle.lean, Phase.lean, Branch.lean, Ends.lean | the 27 rules and the cycles' k-fold repeats, for all sizes (level 2) | Kernel |
blank_O | blank tape reaches O 14 37 11 in 29,301 steps | Kernel |
table_run | 196 moves from O 14 37 11 to the last state | Kernel |
mv_* | the 20 cases of the map on ten forms (level 3) | Kernel |
Good, good_step | the invariant; good leads to good (level 4) | Kernel (omega) |
good_last | the last state is good | Kernel (decide) |
nonhalting | glues the pieces together (the induction of the picture above) | Kernel |
The file lean/Blank.lean does contain one native_decide (a check that the first
107 steps do not halt), but nonhalting does not use it. It is a side fact, shown in the
ledger below.
Other checks, separate from Lean Computed: the first 49 states of the replay
match the plain run up to 3·1010 steps (c/checkpoints.c), and your browser repeats the first
ones in the level 3 section and every rule turn up to 108 steps in the first panel. The replay itself
goes on without a gap to 10300 steps (2,281 states). What the proof does not do is explain the growth
rate; the replay suggests that each pair of phases multiplies the counts by a factor that depends on the residues
taken.
The end of lean/Closed.lean, theorem by theorem:
gOp, gO0, gS1, gRF, gEF, gT3, gT2, gU3, gRG, gRG3).step_Op … step_RG3), each split by remainder or parity into the 20 cases.blank_O then table_run).¬ HaltsFromBlank. By induction on N: for every N there is a run from blank of length at least N ending at a good tape. So runs of every length exist, and the machine does not halt.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.465). 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.529).
After 109 steps the tape spans 56,767 cells (8,385 left of the start, 25,003 right), with a density of 1s of 0.367.
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:
| side | step | tape |
|---|---|---|
| left | 721,587,320 | A>0 0^6 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 |
| left | 976,078,402 | A>0 0^6 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 |
| left | 991,744,076 | A>0 0^6 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 0^3 1 |
| right | 939,130,636 | 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 |
| right | 954,773,681 | 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 |
| right | 970,410,556 | 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 |
These are measurements of one bounded run, sorted by tools/py/bbtools/triage.py; the macro structure behind them is the subject of the levels above, and the Lean proof settles the question.
Status as of 9 November 2026. The same list as the proof-status page, built from the same file.
step_none_iff, lean/Blank.leanThe machine stops exactly when it reads the symbol of a halting transition (B1); the generated statement covers every configuration.
blank_runs_kernel, lean/Blank.leanThe 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.
blank_runs_native, lean/Blank.leanThe same run, evaluated by compiled code.
holdouts/triage.jsonThe C simulator tools/c/triage.c runs 109 steps without a halt; at the end 56,767 cells have been visited and 20,806 of them hold a 1.
tools/py/bbtools/triage.pyLeft 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.465). 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.529).
halt_route, lean/Route.lean (written by py/route.py)Two steps before any halt the machine is in 0 D>x 1 1, D>1 1 1 or 0 D>0; no other configuration halts within three steps.
pass_10_right, pass_10_left, fill_F, fill_B, clear_A, lean/Rules.leanC moving right crosses (10)n unchanged; A moving left crosses (01)n (8 steps a copy); F turns (1000)n into (1110)n and B turns 0 (0001)n into (1110)n 0 moving right; A turns (0111)n into (0010)n moving left. All for any n.
halt_A, halt_F, lean/Rules.leanA>0 1 and F>1 1 halt after two steps; these are the only ways into B reading a 1.
py/shape.py 6.5e6 LRFrom step 1,896,095 to about 6.38·106 the head never reaches the left end. At the right-end visits the tape is (1110)170 (1111110)k 111 001 (10)m with k + m = 578 (k = 12 at step 2,148,568, 468 at step 6,188,728).
py/shape.py 1e7 L 25At the left-end visits from 824,136 to 1,896,095 the tape is 0… (1000)a (10)b wc plus short joints, with (a, b, c) going from (80, 219, 59) to (165, 555, 3). The next such phase starts at step 6,384,890 with c = 287.
cycle, cycle_iter, lean/Cycle.lean (written by py/cycle.py)Inside an odd round-trip phase the left-end visits repeat a cycle of four tape shapes. With S1 a b c = 0∞ A> 07 (1000)a 0000 1 00000 1 000 (10)b (00100000100000)c 001 00000 1 000 101, the machine goes from S1 a (b+2) (c+2) to S1 (a+3) (b+14) c in 80a + 72b + 1356 steps, for all a, b, c; cycle_iter applies it k times. Step 824,136 from blank is S1 80 219 59; the same cycle, with (a, b, c) = (30424, 87941, 19564), is running at step 1.044·1011 (c/phases.c).
cycle2, cycle3, cycle2_iter, cycle3_iter, lean/Cycle.leanAn even round-trip phase runs a 5-visit cycle on T3 a x d y z c = 07 (1000)a (10)x (0010)d (10)y 0000 1 00000 1 000 (10)z (00100000100000)c …, which goes to (a+4, x+8, d−5, y+7, z+5, c−2), and then a 3-visit cycle on T2 a x y c = 07 (1000)a 0000 1 00000 1 000 (10)x 0 (01)y (00000001000001)c 000 101, which goes to (a+3, x+7, y+5, c−2). Both are proved for all sizes, with their k-fold iterates.
odd_phase, oentry, oexit, rcyc_iter, rend, lean/Phase.lean (written by py/phase.py)With O a b c = 0∞ A> 07 (1000)a (10)b (00001000001000)c 101 and EF a q = 0∞ E> 00000 (0001)a (00000100000001)q 00000 1 07 1 00000 1 000 101: from O a (2p+7) (2j+3) the machine reaches EF (a+4+3j) (p+6j+8), for all a, p, j. The proof chains the entry into the 4-visit cycle, j turns of it, the exit into a right phase, the right-phase cycle (one copy of 10 becomes one copy of 1111110, proved for any number of turns) and the start of the next even phase. The odd phases starting at steps 29,301, 808,896 and 27,629,379 (O 14 37 11, O 79 219 61, O 467 1283 361) meet its conditions, and the even phases the simulation finds next are EF 30 47, EF 170 288 and EF 1008 1720.
eentry, texit0–texit4, ucyc_iter, t2exit0/1, uexit0/1, gcyc_iter, g3cyc_iter, gend', g3end', sexit0, lean/Branch.lean (written by py/branch.py), gendo', g3endo', rende', ozero, lean/Ends.lean (written by py/ends.py)Besides the cycles and odd_phase, Lean proves for all values of the parameters: the entry of an even phase, EF (a+7) (q+5) → T3 5 14 a 8 7 (q+2); the five exits of its 5-visit cycle by the number d < 5 of 0010 left (d = 0, 3, 4: two runs of 10 merge into T2; d = 1, 2: three runs, the middle one frozen, form U3); the 4-visit cycle of U3; the exits of the two- and three-run round trips into right phases RG and RG3, for both parities of the 14-cell words left; the cycles of those right phases; their ends when the run of 1111011 has even length (into O, or into T2); and the exit of the 4-visit cycle with no 14-cell word left (sexit0, into the right phase RF). lean/Ends.lean adds the other parities: RG and RG3 ending with an odd run of 1111011 start a 5-visit round trip T3 directly (gendo', g3endo'), and RF ending with an even run of 1111110 gives O a 0 c (rende'), which is an S1 after one pass (ozero, t3_s1). With these every form has a rule for each residue of its counts. Every rule is a symbolic run checked by the kernel, followed by a re-bracketing proof. Each rule states its exact step count.
table_from_blank, lean/Table.lean (written by py/table.py from the replay py/macro.py)From blank tape the machine reaches O 14 37 11 in 29,301 steps (blank_O). From there, 196 moves, each a rule of the table or a k-fold iterate of a cycle with concrete arguments, reach T2 34158019330534 128092572489511 160237983842729 41908435347077 (table_run, table_from_blank), at step 572,161,236,689,394,206,666,641,378,531 by the rules' step counts. The first odd right-phase end, RG 3564802 8141369 4104765 1 at step 1.08·1015, is among them. py/table.py 1e300 writes the 2,280 moves to step 5.6·10299, which Lean also checks (about 90 seconds).
py/macro.py --checkpoints, c/checkpoints.cpy/macro.py replays the run with the table's rules only and predicts 49 configurations before step 3·1010, each with its exact step. The plain C simulator (c/checkpoints.c) finds every one of them on the tape at exactly that step: state, head position and every cell. The phase boundaries of c/boundaries.c (29,301, 191,775, 808,896, 6,370,604, 27,629,379, 223,234,215, 3,043,404,308, 22,249,365,380) are among them. So within 3·1010 steps every branch the run takes is in the table.
Good, good_step, mv_*, lean/Closed.lean (written by py/closed.py)Good gives, for each of ten forms (O a b c with b large, O a 0 c, S1, RF, EF, T3, T2, U3, RG, RG3), 3 to 16 linear inequalities with integer coefficients: the growing counts keep their ratios in a polyhedral cone that every move maps strictly inside the next one; the bounded counts stay in range and T3, U3, RG3 keep exact relations (for example x = 2a + 4 in T3); and a positive linear size, which every move multiplies by at least 1.1, stays above a threshold. These give every offset the rules need, and c ≥ 2⌊d/5⌋ + 3 in T3, so the 5-visit cycle never runs out of words. good_step proves each of the 20 cases with one move lemma and omega; the end of table_from_blank satisfies Good (decide).
nonhalting, lean/Closed.leanFrom good_step and table_from_blank: the run from blank tape is defined for every length. #print axioms nonhalting lists propext, Classical.choice and Quot.sound; no native_decide.
py/closed.pyNot part of the proof. The forms' counts at the form entries along the replay, divided by their sum, give a cloud of points per form. A fixpoint of linear programs over the 20 moves (homogeneous parts, margin 10-3) enlarges their convex hulls until each move maps every cone inside the next; a second linear program finds the size function. Along the replay every form entry from the 39th on satisfies Good.
. /etc/profile.d/lean.sh # after scripts/setup-lean.sh
holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/lean/check.sh
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB 1000000000
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/route.py # writes lean/Route.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/rules.py # writes lean/Rules.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/cycle.py # writes lean/Cycle.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/phase.py # writes lean/Phase.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/branch.py # writes lean/Branch.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/ends.py # writes lean/Ends.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/table.py # writes lean/Table.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/closed.py # writes lean/Closed.lean
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/macro.py # the replay, to 1e300 steps
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/macro.py --checkpoints checks.txt 3e10
gcc -O2 -o checkpoints holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/c/checkpoints.c && ./checkpoints checks.txt
gcc -O2 -o boundaries holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/c/boundaries.c && ./boundaries 3e10
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/shape.py 1e7 L 25
python3 holdouts/1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB/py/shape.py 6.5e6 LR 60