Busy Beaver Explorer / holdouts / 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA / explained

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

Does this machine ever halt?

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.

native_decideno haltLean theorem nonhalt; the rounds of 1,144 classes evaluated by compiled code.
KernelexecutorThe symbolic executor that runs the rounds, and the test that the set is closed, are proved sound in Lean.
native_decide1,144 classesA closed set of round ends (62 tails, the block size by its remainder); none reaches the halting transition.
Computed1,302 roundsOf the real run, block sizes up to 437 digits, agree with the classes exactly.
Computed5 halting classesFound among nearby tapes with a slightly different tail: the shape alone does not prevent a halt.
Also proved in CoqA second proof assistant checks the same result: 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.
Community labelIn the community's BB(6) tracker the machine's class is Bell-like. 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 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 >.

statereads 0reads 1
A1 R B0 R D
B1 R C0 L F
C1 L A0 L B
Dhalt1 R E
E1 L B1 R A
F0 L C0 R 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 1,144 classes

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.

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 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.

event 1,001 of the run
Round ends:
1 · Machine
first three cellsleft block (01)^abig block (01)^btail Tdark = 1, pale = 0; the triangle is the head, state A
2 · Blocks
3 · Cycle rule
4 · Round
The step counts are exact: the browser counts every step from blank tape. Event 3,600 is about 1.2·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 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:

sidesteptape
left956,363,500C>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
left972,062,110C>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
left987,988,562C>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
right961,538,1380 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
right978,051,1880 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
right993,829,5970 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.

Level 1 to level 2

Two blocks and a tail

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 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

The tail runs in a cycle

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 periodeventsleft blockbig blockratioLean
15 (three variants)30−45 pairs+99 pairs2.2rule1_ok, rule3_ok, rule5_ok
1632−48+992.06rule0_ok
2244−66+1412.14rule2_ok
918−27+572.11rule4_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).

Both blocks get the same x here. The browser writes the template on a blank tape, puts the head on its first cell in state A, runs the real machine until state A has reached the left end the rule's number of times, and compares the tape with the template after.

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.

Level 3 · Try it

Drain the left block yourself

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.

Level 3 to level 4

When the left block is empty

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.

The long run takes the browser some 10 to 30 seconds; it runs in slices, so the page stays usable. "Tail" gives the position of the round end's tail in the list of 62 tails of the closed set (lean/ClassData.lean), or "none".
Level 4

A closed set of 1,144 classes

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.

From B = 28,531 and its tail, follow
Each round: find the class whose tail is T and whose r0 ≤ B ≡ r0 (mod m), set x = (B − r0) / m, then B becomes k + c·x and T the next tail. Exact integer arithmetic (BigInt). That such a class is always found is what the coverage test guarantees; that the machine really goes there is 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).
How sure

What this rests on

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.

A warning

Nearby tapes do halt

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.

The tape is 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.
The bottom line

It never halts

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:

  • The Lean kernel checks the soundness of the symbolic executor (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).
  • Sixteen evaluations by 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.
  • Not used: the Python search that found the classes, or any simulator outside Lean. The executor's choices (which rule, how many times, how to re-bracket) are not trusted; only its soundness is, and that is proved.
  • Not stated in Lean: step counts, such as the step 2,340,515,329 of the first round end in a class; Lean says only "reaches, in at least one step". Those come from the simulators (computed).

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.

Side by side

This run next to a related machine

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.

1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA (this machine)

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 (D0); 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 38,989 cells have been visited and 19,487 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
lean/Rules.lean (generated by py/rules.py)
Sweeps over the long blocks

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).

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

From 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.

Kernel
coq/H11019.v, coq/SymExecN.v; build: sh coq/build_H11019.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 2.5 min.

Kernel
nonhalting_of_closed_set, lean/Closed.lean
A closed set of round ends implies that it never halts

If 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.

Kernel
lean/Exec.lean, lean/Classes.lean; shRTbl_ok, shLTbl_ok in lean/ExecData.lean
A symbolic executor and the two class tests, proved sound

The 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.

native_decide
rule0_ok … rule5_ok, lean/ExecData.lean
Six cycle rules of the tail, for all values of their counts

Each 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.

native_decide
reach_set, lean/Replay.lean; lean/Arrive.lean
Blank tape reaches the round end with B = 28,531

527,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).

native_decide
closed_set, classes_ok, lean/Replay.lean; chunk0_ok … chunk7_ok, lean/Chunk0.lean …; data lean/ClassData.lean
The 1,144 classes are closed under one round

For 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.

Computed
py/closure/accel.py (verify, selftest)
The tail cycles

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.

Computed
py/closure/closure.py, py/closure/cert.json
The closed set: how it was found, step counts

A 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.

Computed
py/closure/validate.py real, c/ev.c
The real run enters the closed set: step count, later rounds

That 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.

Computed
py/closure/validate.py plain | mutate, c/round.c
Checks of the simulator

Five 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.

Computed
py/closure/validate.py tails | neighbours
Nearby tapes that halt

The 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.

Computed
verify/README.md, verify/run_all.sh
Independent check of the closed set

A 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.

Computed
holdouts/related.json, written by holdouts/related.py compute (tools/c/cfgmatch.c, tools/c/lockstep.c)
Related holdouts

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.

Check it yourself

Commands

. /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)