Busy Beaver Explorer / holdouts / 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA / explained
A 6-state Busy Beaver machine · Status as of 13 November 2026.1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA
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 long blocks on this machine's tape act like two buckets: at every visit of the left end a little is poured from the left one into the right one, which grows about twice as fast as the left one shrinks. When the left one is empty the right one takes its place. A short stretch at the right end, the tail, decides how much is poured; at the end of a round it is always one of 62 words, and from none of them does the machine stop.
nonhalt; the rounds of 1,144 classes evaluated by compiled code.H11019.nonhalt : ~ halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/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 (a 668-line checker for tapes with two blocks of unknown length and a 58-line file with four seed tapes; Coq 8.20.1 checks it in about 25 seconds) is on a branch of our fork of busycoq, ready to be proposed upstream: bb6-nonhalt-1RB0RD_1RC0LF_1LA0LB_HHH1RE_1LB1RA_0LC0RA.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 D reading 0. D is entered only from A1 (writes 0, moves R): A>1 0. So a halt is the moment this pattern appears, with the head on the cell after >.
| state | reads 0 | reads 1 |
|---|---|---|
| A | 1 R B | 0 R D |
| B | 1 R C | 0 L F |
| C | 1 L A | 0 L B |
| D | halt | 1 R E |
| E | 1 L B | 1 R A |
| F | 0 L C | 0 R A |
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?" 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 two long blocks of pairs 01 and a short
tail, at the moments state A reaches the left end; whole periods of the tail's cycles, each a rule that holds for
every size of the two blocks; and finally the ends of rounds, sorted into 1,144 classes that lead only into each
other and never to the halting transition.
blank_runs_native)
Level 2Two blocks and a tail
010 (01)^a 000 (01)^b T as cells and blocks, looked at when state A reaches the left end (an event). One unit is one move of the executor: a whole block crossed by a shift rule, or one step.run_sound, the 15 shift rules shRTbl_ok, shLTbl_ok
Level 3The tail's cycles
b + 3x that comes back after 18 to 44 events, a smaller by 27 to 66 pairs and b larger by 57 to 141. One unit is one period; N periods are one move.rule0_ok … rule5_okrule_instN
Level 4Round ends node B T
01001000 (01)^B T when the left block is used up: a tail T and a number B. One unit is one round.chunk0_ok … chunk7_ok; the run gets there: arrive_ok, start_okclosed_of_checks, nonhalting_of_closed_set
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 two blocks and the tail, the cycle rule of the Lean proof whose template the tape fits (if any), and the round the moment belongs to. Where a rule fits, the browser runs the machine on to the end of the rule's period and checks that it arrives exactly where the rule says.
(01)^abig block (01)^btail Tdark = 1, pale = 0; the triangle is the head, state ALeft 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).
After 109 steps the tape spans 38,989 cells (7,943 left of the start, 18,839 right), with a density of 1s of 0.5.
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 | 956,363,500 | C>0 0^2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 |
| left | 972,062,110 | C>0 0^2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 |
| left | 987,988,562 | C>0 0^2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 |
| right | 961,538,138 | 0 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 |
| right | 978,051,188 | 0 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 |
| right | 993,829,597 | 0 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 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.
Seen at the moments when the head, in state A, arrives at the left end (an event), the tape is, for most of the run,
010 (01)^a 000 (01)^b T
Here (01)^a means the pair 01 written a times. The left block has a pairs, the big
block has b pairs, and T, the tail, is a short word made of a few small blocks of pairs separated by
000 or 111. Example, step 9,932,715,748: a = 2,110, b = 56,419, and the tail has blocks of 4,
13, 16 and 20 pairs.
One visit of the left end: the head crosses the whole tape to the right and back, twice. On the way it takes
exactly 3 pairs from the left block, and the tail changes a little: its small blocks shrink by 3 pairs each, a
block that is used up merges into its neighbour, and from time to time a block is absorbed into the big block. In the
long stretches the events come in pairs six steps apart, first 110 … and then
010 …, so one visit is two events. The five crossings of the long blocks in a visit are proved in
Lean for blocks of any length, three pairs at a time, by the kernel alone (c_right6,
a_left6, b_right6, b_left6, f_left6 in
lean/Rules.lean).
The Lean proof works at this level with a symbolic executor (adapted from the one of
1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA): 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 either crosses a whole block with a shift rule
(in state q, with the word u just behind the head, k copies of w are crossed and the word v is left behind, in s
steps), or makes one ordinary step. Each of the 15 shift rules is a 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, the machine does, for every value of the unknown. That is the theorem
that makes level 2 answer the same as level 1.
The tail does not grow. After a start-up of some dozens of visits it repeats with a fixed period, and in one period fixed amounts leave the left block and enter the big block. Four such cycles occur:
| visits in a period | events | left block | big block | ratio | Lean |
|---|---|---|---|---|---|
| 15 (three variants) | 30 | −45 pairs | +99 pairs | 2.2 | rule1_ok, rule3_ok, rule5_ok |
| 16 | 32 | −48 | +99 | 2.06 | rule0_ok |
| 22 | 44 | −66 | +141 | 2.14 | rule2_ok |
| 9 | 18 | −27 | +57 | 2.11 | rule4_ok |
Each line is a cycle rule in lean/ExecData.lean: a template of the whole tape,
A> 110 (01)^a 000 (01)^b T with a = a0 + 3x and b = b0 + 3y, that comes back with
a smaller and b larger by the amounts in the table, for all x and y. Each is proved by one run of the executor
itself, without cycle rules, from the template before to the template after, 9,143 to 25,749 moves, evaluated by
native_decide (ruleOK_of_run is the kernel theorem that turns such a run into the rule).
Inside a round the executor applies a rule N times in one move, where N may itself be N0 + q x: the
left block is r0 + m x and each period eats d = 27, 45, 48 or 66 pairs of it, so N = N0 + (m / d) x.
The N-fold rule is proved by induction (rule_instN, kernel), and the subtraction is checked coefficient
by coefficient (appTok, app_inst).
The same rules can be looked for in the run itself. The scan below runs the machine from blank tape through its first 3,600 events, tests every event against the six templates, and wherever one fits checks the rule's prediction against the event that many events later.
Within a round the tail runs in one of four cycles, and each period of a cycle moves a fixed number of pairs out of the left block and a larger number into the big block. Pick a cycle and apply it until the left block is nearly empty: the big block ends up 2.06 to 2.2 times as long as the left block was, which is why each round is that much longer than the last. In the real run the tail decides which cycle applies; here you choose, to see the arithmetic.
A round ends when the left block is down to one pair: the tape is then
node B T = A> 01001000 (01)^B T
and during the next two visits the big block (B pairs) becomes the new left block, of B + 3 pairs, with a new small big block. So each round is 2.06 to 2.2 times longer than the one before. Sizes B at the round ends: 586, 1,291, 2,827, 6,280, 12,967, 28,531, …
What the next round end looks like depends on two things only: the tail T, and at which point of its cycle the tail is when the left block runs out. The second is decided by the remainder of B when divided by the amount a period eats (45, 48, 66 or 27). The size of B beyond that plays no role, and that is what makes a finite analysis possible.
The browser can find the round ends of the real run. The first button lists those of the first 1.2·108
steps; the second runs on to the round end where the closed set takes over, which Lean reaches with 527,489 executor
moves (arrive_ok, lean/Arrive.lean) and the simulators place at step 2,340,515,329.
lean/ClassData.lean), or "none".Call a class all round ends with a given tail T and a given remainder of B (and B at least 20,000). For one class the symbolic executor runs one whole round with B = r0 + m·x, where x is an unknown. The result is the next round end: a new tail T' and a new size B' = k + c·x. Whatever x is, B' has one of a few remainders; all of them must be classes of the list. Nothing about x is remembered, so the list over-counts what the real run can do.
Starting from the round end the real run reaches after 2,340,515,329 steps (B = 28,531), the search
(py/closure/closure.py bfs) stops by itself: 62 tails, 1,144 classes, and every class leads only to
classes already on the list. In none of the 1,144 symbolic rounds does the machine reach its halting transition
(state D reading 0). The remainders are not a hidden Collatz problem here: the search never asks which remainder
comes next in the real run, it accepts all of them.
In Lean (lean/Classes.lean, lean/ClassData.lean) each class is a record (tail, r0, m, K,
next tail, k, c), and two tests are evaluated for every class by native_decide, 143 classes to a chunk
(chunk0_ok … chunk7_ok): clsRun, the executor's round of K + 1 moves from
node (r0 + m x) tail with x free must end at node (k + c x) next; and covers,
for every j below a common multiple P of the moduli of the next tail's classes, some class of that tail must contain
B' = k + c·j, with c·P a multiple of its modulus, so that the same class serves j, j + P, j + 2P, and so
on. The kernel proves what the two tests mean (clsRun_sound, covers_sound) and that a list
passing both is closed (closed_of_checks); with the arrival, nonhalting_of_closed_set
(lean/Closed.lean, kernel) gives the theorem.
The panel below holds the 1,144 records as they are in lean/ClassData.lean. The browser runs the
coverage test, as written in Classes.lean, and follows the run from B = 28,531 through the classes. The
rounds themselves (clsRun) take about 4·109 machine steps each, too many for the browser;
they are what Lean evaluates.
clsRun. py/closure/validate.py real compared 1,302 consecutive rounds of the real run with the classes, B up to 437 digits, all exact; 684 classes and all 62 tails occurred (computed).The closed set was found by our own symbolic simulator. It is now also a Lean proof: a second program of the same kind (a symbolic executor: it crosses whole blocks at once and applies a proved cycle many times in one go, a number of times that may depend on the unknown x) is written in Lean and proved correct once: whatever it does, the machine does, for every x. Lean then runs it on each of the 1,144 classes with x unknown, 133 million moves in all, and on the run from blank tape, and checks by a proved test that every round end it arrives at is on the list. Those runs are done by compiled code (native_decide), the one thing trusted beyond Lean's kernel.
What was done before that to test the first simulator, and still supports the step counts quoted here:
Lean's kernel alone proves the five sweeps for blocks of any length, the executor's correctness, and the last step of the argument: a closed set of round ends that the run enters implies that it never halts.
The shape 01001000 (01)^B T alone does not keep the machine running. Take one of the 62 tails and make
one of its small blocks one pair longer or shorter: of 1,141 such classes tried, 1,136 fall back into the closed set
after one round, but 5 halt, for every size B. One of them, checked cell by cell: with the tail
0000 (10)^10 000 (10)^4 000 (10)^12 111 0000 101 (the last block has 12 pairs; the closed set has this
tail with 11) and B = 20,002 + 3x, the machine halts after 815,565 + 122x steps (computed by
py/closure/validate.py tails, confirmed bit by bit at x = 0, 1, 3).
So the argument really needs the exact list of 62 tails; a statement about all tails would be false. Other remainders of B for the 62 tails are harmless: all 1,722 classes tried fall into the closed set.
The browser can run the halting neighbour, and the tail of the closed set next to it.
A> 01001000 (01)^(20,002 + 3x) T. With the tail of the closed set the browser stops after 2·107 steps; a whole round from there takes about 4·109 steps. These round ends lie in classes of the list, so that the run from them goes on from class to class for ever follows from the Lean theorem closed_set, not from a bounded run.It never halts.
Started on a blank tape, 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA runs for ever. From step 2,340,515,329 on, every round end of its run lies in one of 1,144 classes, every class leads after one round only to classes of the same list, and no round of any class reaches the halting transition.
The Lean theorem is nonhalt : ¬ HaltsFromBlank in lean/Replay.lean, ledger level
native_decide. What it rests on, exactly:
run_sound, run_pos,
rule_instN, ruleOK_of_run in lean/Exec.lean), what the two class tests mean
(clsRun_sound, covers_sound, closed_of_checks, arrives_sound,
inSetB_sound in lean/Classes.lean), the 15 shift rules (each by rfl), and the
last implication, nonhalting_of_closed_set (lean/Closed.lean).native_decide, which trust Lean's compiler as well as its kernel: the six
cycle rules (rule0_ok … rule5_ok), the eight chunks of 143 classes
(chunk0_ok … chunk7_ok, a round with x free and the coverage test for each class),
the arrival from blank tape (arrive_ok, 527,489 moves) and its class (start_ok).
#print axioms nonhalt lists propext, Classical.choice, Quot.sound
and these sixteen evaluations; there is no sorry.There is no kernel-only proof yet: the long runs would have to be cut at checkpoints, which has not been done. A
second proof of the same statement, in Coq on top of busycoq (coq/H11019.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.
The two machines run for the same number of steps and are drawn the same way, a row each time the head reaches a new cell. Where the relation involves a mirror image, the second diagram is flipped left to right so that the two can be compared directly. Look for where the pictures agree and where they part: the text under each relation in the section on related machines says which of it is proved and which is only observed.
Status as of 13 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 (D0); 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 38,989 cells have been visited and 19,487 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.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).
lean/Rules.lean (generated by py/rules.py)Eight shift rules, for every number n of words and every surrounding tape. The five sweeps of one visit of the left end, three pairs at a time: 1 C>(010101)^n → (011001)^n 1 C> (14n steps); (011001)^n A>110 → A>110 (010101)^n (22n); 1 B>(010101)^n → (010110)^n 1 B> (14n); (010110)^n B>000 → B>000 (010101)^n (22n); (011001)^n F>0 → F>0 (010101)^n (22n). And three earlier ones (f_left, b_right, e_right).
nonhalt, lean/Replay.leanFrom blank tape the machine never reaches a halting configuration: nonhalt : ¬ HaltsFromBlank, from nonhalting_of_closed_set with the set of the 1,144 classes and the three claims below. Axioms used: propext, Classical.choice, Quot.sound and 16 compiled evaluations (native_decide): the arrival, the start node's class, eight chunks of classes, six cycle rules.
coq/H11019.v, coq/SymExecN.v; build: sh coq/build_H11019.sh /path/to/busycoqThe 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 2.5 min.
nonhalting_of_closed_set, lean/Closed.leanIf the run from blank tape reaches a round end A> 01001000 (01)^B T that belongs to a set S, and every round end in S reaches a round end in S after at least one step, then the machine does not halt. Its two hypotheses are proved by the replay below.
lean/Exec.lean, lean/Classes.lean; shRTbl_ok, shLTbl_ok in lean/ExecData.leanThe executor of 1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA, adapted: tapes of cells and blocks (w)^n with n = c + a·x; shift rules with a carried word, one to three copies at a time; one machine step; at each arrival of state A at the left end a re-bracketing and a cycle rule applied N times, where N may itself be a count N0 + q·x (the subtraction is checked coefficient by coefficient). Any step that would depend on x fails. Theorems: whatever the executor does, the machine does, for every x (run_sound); a class whose run ends at the announced round end does so for every x, in at least one step (clsRun_sound); the coverage test, a finite check over one period of the remainders, implies that every announced B lies in a listed class (covers_sound); a list that passes both is closed (closed_of_checks). The 15 shift rules are proved by evaluation in the kernel.
rule0_ok … rule5_ok, lean/ExecData.leanEach rule says: this tape 110 (01)^a 000 (01)^b T with a = a0 + 3x, b = b0 + 3y comes back, 18 to 44 visits of the left end later, with a smaller by 27 to 66 and b larger by 57 to 141, for all x and y. Each is one run of the executor without cycle rules (9,143 to 25,749 moves), evaluated by native_decide.
reach_set, lean/Replay.lean; lean/Arrive.lean527,489 moves of the executor from blank tape end at 01001000 (01)^28531 T with the tail of the certificate, and that round end is in a class of the list (arrive_ok, start_ok, native_decide).
closed_set, classes_ok, lean/Replay.lean; chunk0_ok … chunk7_ok, lean/Chunk0.lean …; data lean/ClassData.leanFor each class (tail T, B = r0 + m·x) the executor runs one round with x free (60,000 to 231,000 moves, 132,636,430 in all) and ends at the round end with tail T' and B' = k + c·x of the certificate; every such B' lies in a listed class. So every round end of the set reaches a round end of the set in at least one step. Eight native_decide evaluations of 143 classes each, 35 to 56 s each.
py/closure/accel.py (verify, selftest)Within a round the tape is 010 (01)^a 000 (01)^b T. After a start-up the tail T repeats with a fixed period: 15 visits of the left end (a − 45, b + 99; three different tails), 16 visits (a − 48, b + 99), 22 visits (a − 66, b + 141) or 9 visits (a − 27, b + 57). Each cycle is established by one symbolic run with a and b free (steps affine in both) and re-checked on numbers.
py/closure/closure.py, py/closure/cert.jsonA class is a tail T (62 of them) and a remainder of B (modulo 66: 682 classes; 45: 300; 48: 144; 27: 18), with B ≥ 20,000. For each class one symbolic round with B = r + m·x, x free, ends at 01001000 (01)^B' T' with B' = k + c·x (c = 141, 99 or 57, k ≥ 41,224); every remainder B' can have lies in a class again. The simulator refuses any step whose outcome depends on x. closure.py check re-runs all classes and tests the coverage independently of the search (5 minutes). That the set is closed is now a Lean theorem (above); this tool found it and supplies the step polynomials.
py/closure/validate.py real, c/ev.cThat blank tape reaches the round end with B = 28,531 is a Lean theorem (above). Computed: from blank tape the run is at the round end with B = 28,531 after 2,340,515,329 steps (the plain C simulator gives the same step), in the class B = 19 mod 66 of its tail. The next 1,302 rounds (B up to 437 digits), computed with numbers, agree with their classes: next tail, next B and the number of steps, all exact; 684 of the classes and all 62 tails occur.
py/closure/validate.py plain | mutate, c/round.cFive classes at x = 0 and x = 1 against a bit-level simulator (4.1 to 4.3 · 109 steps each): state, head position, tape and step count exact. 12 defects injected into the certificate and 8 into the simulator (wrong rule increments, rules without lower bound, wrong number of rule applications, three changed transitions, a class claimed for too coarse a remainder): all 20 reported.
py/closure/validate.py tails | neighboursThe same shape with another tail can halt: of the tails that differ from one of the 62 by one pair 10 in one block (a sample, 1,141 classes), 5 classes halt for every B, for example tail 000010101010101010101010000101010100001010101010101010101010101110000101 with B = 20,002 + 3x halts after 815,565 + 122x steps (confirmed bit by bit at three values). The other 1,136 fall into the closed set after one round. Other remainders of B for the 62 tails (a sample, 1,722 classes) all fall into the closed set; none halts.
verify/README.md, verify/run_all.shA second accelerated simulator written from scratch, without the first tool's engine (verify/accel.cpp, validated against plain simulation up to 4.4·109 steps), confirms the arrival from blank tape at step 2,340,515,329 and, for every one of the 1,144 classes, four members (the two smallest, one B near 106, one near 1011) plus 7,000 random members: no halt, the next round end is exactly the predicted tail, B and step count, and lies in a listed class. 0 mismatches; the five neighbouring tails said to halt do halt. It samples B; that every B of a class behaves so is the Lean theorem closed_set.
holdouts/related.json, written by holdouts/related.py compute (tools/c/cfgmatch.c, tools/c/lockstep.c)The same table as 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC up to renaming, started in another state; no common configuration in the first 107 steps of each.
. /etc/profile.d/lean.sh # after scripts/setup-lean.sh
holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/lean/check.sh # all Lean files, 6 to 7 min (the eight chunks of classes take 35 to 56 s each)
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/replay/gen.py --check # the model of the Lean executor: tables, arrival, all 1,144 classes with x free (6 min); without --check it rewrites the generated Lean files
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA 1000000000
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/rules.py > holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/lean/Rules.lean # regenerate the sweep rules
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/closure.py check holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/cert.json # re-run the 1,144 classes, 5 min
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/closure.py bfs /tmp/cert.json # the search itself, 5 min
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py real 120 # the real run against the classes
gcc -O2 -o round holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/c/round.c && python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py plain ./round 5 # bit-level, 3 min
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py mutate cert; python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py mutate engine; python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py mutate engine2
python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py tails 420 7; python3 holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/py/closure/validate.py neighbours 500 12
gcc -O2 -o ev holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/c/ev.c && ./ev 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA 2000000000 L A 1 100000 12 | awk 'NR%300==0'
bash holdouts/1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA/verify/run_all.sh # independent simulator: arrival, all 1,144 classes sampled (about 2 min)