Busy Beaver Explorer / holdouts / 1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB / explained

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

Does this machine ever halt?

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.

Kernelnever haltsProved in Lean by the kernel: a table of phase rules and a linear invariant on the counts.
Computed109 stepsNo halt in the C simulator; 56,767 cells visited.
native_decide107 stepsNo halt, proved in Lean; the first 10,000 by the kernel alone.
Heuristicsqrt/sqrtThe growth shape of the two sides of the tape (see below).
Also proved in CoqA second proof assistant checks the same result: 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.
An outside proof is waiting for review: it never haltsbusycoq pull request 44 (Alk, 2026-11-05) contains a Rocq proof that this machine never halts (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.
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 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 >.

statereads 0reads 1
A1 R B0 L E
B1 R Chalt
C1 R D1 R E
D1 L A0 R F
E0 R C0 L A
F0 L C0 R B
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 a list of inequalities

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.

The way in: 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).

One moment, four descriptions

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.

moment 0
1 · Machine
Each pixel column is one cell or, on a long tape, the share of 1s among a few neighbouring cells (dark = 1). The band under it colours the runs of the form, as in the strip below; the orange mark is the head.
2 · Form and rule
3 · Phase map
4 · Invariant
Level 1

The machine, and the only way it can halt

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.

Level 1 to level 2

The tape is a list of numbers

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

Crossing a run in one move

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.

Level 2

One rule, for any size

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.

Before:
After:
Level 2 to level 3

Ten forms and twenty cases

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.

● round-trip form (head at the left end)
● right-phase form (head at the right end)
×n: times the first 196 moves use it
Form :
Its cases at level 3 (lean/Closed.lean):
Its rules at level 2:

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

Following the map from the blank tape

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

Level 4

Why the moves never run out

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:

shape
the growing numbers keep their ratios inside a fixed region (a polyhedral cone). For 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.
small parts
the bounded numbers stay in range (in 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).
size
one weighted sum is at least 50,000,000 or 100,000,000, such as 71·b ≥ 50,000,000 for 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:

  • the map sends each form's region strictly inside the next form's region, with room to spare;
  • the size grows by a factor of at least 1.1 per case, so the room to spare grows faster than the fixed offsets in the formulas (the "+6", "+13" and so on);
  • the inequalities imply every condition a case needs (b ≥ 6 and so on), and that T3 has c ≥ 2⌊d/5⌋ + 3, enough 14-cell words for all its turns. That rules out the gaps of level 3.

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

It never halts

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.

Blank tapestate A, all 0s 29,301 stepsto the form O 14 37 11blank_O 196 proved movesto T2 at step 5.7·10²⁹table_run Good tapeone of 10 forms, withits inequalities true good_last One move20 cases, good_step Never haltsnonhalting 27 rulesproved for allsizes, used byboth of the above
Kernel green boxes: every box is checked by Lean's kernel

What every piece rests on

A wrong number anywhere, in the replay or the inequalities, cannot make the proof pass. It would only make one of the checks fail.

PieceWhat it saysChecked by
Machine.leanthe machine's table and what a step is (generated from the machine's name)Kernel
Rules.leanthe five passes, for any n; the two halting patternsKernel
Cycle.lean, Phase.lean, Branch.lean, Ends.leanthe 27 rules and the cycles' k-fold repeats, for all sizes (level 2)Kernel
blank_Oblank tape reaches O 14 37 11 in 29,301 stepsKernel
table_run196 moves from O 14 37 11 to the last stateKernel
mv_*the 20 cases of the map on ten forms (level 3)Kernel
Good, good_stepthe invariant; good leads to good (level 4)Kernel (omega)
good_lastthe last state is goodKernel (decide)
nonhaltingglues 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 last lines of the proof, in words

The end of lean/Closed.lean, theorem by theorem:

Good t
t is one of the ten forms, with numbers that satisfy that form's inequalities (gOp, gO0, gS1, gRF, gEF, gT3, gT2, gU3, gRG, gRG3).
good_step
from a good t, at least one step leads to a good t′. One case per form (step_Op … step_RG3), each split by remainder or parity into the 20 cases.
table_from_blank
some run from the blank tape ends at the last state of the replay (blank_O then table_run).
good_last
that last state is good.
nonhalting
¬ 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.
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.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).

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

sidesteptape
left721,587,320A>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
left976,078,402A>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
left991,744,076A>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
right939,130,6361^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
right954,773,6811^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
right970,410,5561^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.

What is known

Every result, by what it rests on

Status as of 9 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 (B1); 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 56,767 cells have been visited and 20,806 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.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).

Kernel
halt_route, lean/Route.lean (written by py/route.py)
Every way to a halt

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.

Kernel
pass_10_right, pass_10_left, fill_F, fill_B, clear_A, lean/Rules.lean
Five passes

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

Kernel
halt_A, halt_F, lean/Rules.lean
The halting situations

A>0 1 and F>1 1 halt after two steps; these are the only ways into B reading a 1.

Heuristic
py/shape.py 6.5e6 LR
A right phase

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

Heuristic
py/shape.py 1e7 L 25
A round-trip phase

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

Kernel
cycle, cycle_iter, lean/Cycle.lean (written by py/cycle.py)
The 4-visit cycle, for all sizes

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

Kernel
cycle2, cycle3, cycle2_iter, cycle3_iter, lean/Cycle.lean
The two cycles of an even phase

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

Kernel
odd_phase, oentry, oexit, rcyc_iter, rend, lean/Phase.lean (written by py/phase.py)
A whole odd phase and the right phase after it

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.

Kernel
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)
The branch table, for all sizes

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.

Kernel
table_from_blank, lean/Table.lean (written by py/table.py from the replay py/macro.py)
The table carries the run to step 5.7·1029

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

Computed
py/macro.py --checkpoints, c/checkpoints.c
The replay agrees with the simulation up to 3·1010 steps

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

Kernel
Good, good_step, mv_*, lean/Closed.lean (written by py/closed.py)
The invariant

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

Kernel
nonhalting, lean/Closed.lean
It does not halt from blank tape

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

Heuristic
scratch scripts (scipy); the resulting inequalities are the data in py/closed.py
How the invariant was found

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

Check it yourself

Commands

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