Busy Beaver Explorer / holdouts / 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE--- / explained
A 6-state Busy Beaver machine · Status as of 13 November 2026.1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---
Decided: it haltsProved in this repository, checked by Lean and by Coq. The ledger below says what each part rests on.
Yes, it halts, and Lean has checked the proof. Behind two counters ticking together this machine is a small rewriting system: blocks 000/100 that act as binary digits, blocks 1010 that double the visits passing through, and a block 1011 that stops the machine. For 161,210 rounds the trap never forms; in round 161,211 it does. Nobody could watch that happen: it takes about 1024,266 steps.
halts_from_blank, proved in Lean (kernel + native_decide for the checker run).1011.M_1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1REHHH.halts : halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in tools/coq/busycoq/VisitLaw2. Coq 8.20.1 compiles it and Print Assumptions reports no axioms; the build log is next to the files. It runs the same visit law for 161,210 rounds with the checker of busycoq pull request 59, extended to two forms of visit; that run is one evaluation of about 15 minutes. The same files are on a branch of our fork of busycoq, ready to be proposed upstream: bb6-halt-1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1REHHH.Each entry says what to write, which way to move and which state to enter. The machine starts in A on a blank tape (all 0s).
The machine stops when it is in F reading 1. F is entered only from C1 (writes 0, moves R): C>1 1. 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 L B |
| B | 0 R C | 0 L E |
| C | 1 R D | 0 R F |
| D | 1 L B | 1 R B |
| E | 0 L A | 1 R B |
| F | 1 R E | halt |
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.
"Does this machine halt?" is answered here by walking down five levels of description. Each level forgets detail the one above it keeps, and each step down is a Lean theorem that carries the answer back up: a halt found at a lower level is a halt of the level above. At the bottom there is no machine left, only one computation, and running that computation is the last link of the proof (the bottom line).
0∞ A> 1 0 0 S; a round is one
visit to the word 1 0 S, which makes visits of its own, entered in state C or F. One unit is one round.start, round, round_halts, V_*, W_*
Level 3Four rules on words
1011, and no machine in it.
One unit is one visit.law, Law.av, Law.ah
Level 4Counting visits
scan_sound, hscan_sound, halts_of_check
Level 5One evaluation
check 161210 [true] = true: 161,210 rounds of the pass, then a round that meets the trap.
One unit is the whole run, cut into ten segments.check_run
Pick a round. The browser runs the real machine from blank tape until that round starts, finding the moment
on the machine itself (the head two cells further left than at the last round, in state A, on the tape
0∞ 1 0 0 S), and reads the word S off its tape. Separately it runs the visit rules with
their step counts, the rewriting system, and the checker's counting pass, each from its own start. The rows show
the same moment at every level; the check marks say that the computations agree.
1010under a digit1010 double the
visits that pass through them, green blocks are binary digits, grey cells are not reached in that round. Round 36
starts after more than 3·107 steps; the browser runs them in well under a second.Call everything from some cell to the right a stream. A visit: the head stands on a 0 (the lead
cell) with a 0 on its left and a stream s on its right, in state C (form V) or in state F (form W); it comes back
in state A two cells further left, both 0s restored and s rewritten. lean/Visit.lean proves, for every
stream and every tape to the left, what a visit does to a stream according to how the stream begins. The theorems
were produced by running the transition table symbolically on every short beginning of a stream
(py/visit2.py), and each proof is an exact count of the machine's own steps between the nested
visits:
| the stream begins | after the visit | form V (entered in state C) | form W (entered in state F) |
|---|---|---|---|
0 s | 1 s | V_0: 4 steps | W_0: 8 steps |
100 s | 000 v(s) | V_100: 3 steps, then V, 3 steps | W_100: 3 steps, then V, 3 steps |
110 s | 000 v(s) | V_110: 5 steps, then V, 3 steps | W_110: 5 steps, then V, 3 steps |
1010 s | 1010 v(v(s)) | V_1010: 4 steps, then W, 2 steps, then V, 14 steps | W_1010: 4 steps, then W, 2 steps, then V, 14 steps |
1011 s | the machine halts | V_1011_halts: after 4 steps, F reads a 1 | W_1011_halts: after 4 steps, F reads a 1 |
v(s) is what one visit makes of s. The generator also proves V_1110, W_1110 (1110 s becomes 1010 v(v(s))), V_1111_halts and W_1111_halts; the law does not use them.
"Then V" means: the machine makes a visit of its own, in form V, to the stream behind the block, whose lead
cell is the last cell of the block. In this machine both forms obey the same rules (W_0, W_100, W_110, W_1010, W_1011_halts); they differ only in their step counts. A visit in form W is only ever made as the first of the two nested visits behind a doubler 1010. If a nested visit halts, so does the visit around it
(V_100_halts_1, V_1010_halts_1, V_1010_halts_2, ...).
Rounds. From blank tape the machine reaches 0∞ A> 1 0 0 1 0∞
after 6 steps (start). From a tape 0∞ A> 1 0 0 S it takes 8 steps to
stand on the first of these cells in state C, with 1 0 S as its stream, and a visit then brings it to
0∞ A> 1 0 0 S', two cells further left, where S' is what the visit made of
1 0 S (round); if that visit halts, the machine halts (round_halts). So the
whole run is a sequence of rounds, and each round is one visit with visits nested inside it.
Below, the real machine runs through one round. Time runs downwards, one row per step (or per few steps in the long rounds). The dots are where the rules say each visit begins: the step is computed from the step counts in the table, the cell is the lead cell of its stream. The browser checks every one of them against the machine.
Leave out the states, the step counts and the two forms, and what remains is a rewriting system on words. In
VisitLaw.lean it is two inductive relations on streams with no machine in them: AV s s',
"one visit rewrites s to s'", and AH s, "a visit to s halts".
| the stream begins | one visit makes | rule |
|---|---|---|
0 s | 1 s | AV.z |
100 r | 000, and one visit to r | AV.h |
110 r | 000, and one visit to r | AV.g |
1010 r | 1010, and two visits to r, if r does not start with 11 | AV.l |
1011 r | the visit halts | AH.x |
A visit also halts if one of its nested visits halts (AH.h, AH.g, AH.l1,
AH.l2). So a block 000 or 100 is a binary digit: it flips on every
visit and passes every second visit on. A block 1010 is a doubler: it passes every visit on
twice. A block 1011 is the trap.
The guard. The doubler rule carries the side condition "the stream behind does not start with
11" (Guard), because the first of its two nested visits is made in form W. This machine does not need it, since its form W obeys the rule for 110 too; the system is shared with the twin 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA0RE_1RE---, whose form W does not. Lean
proves that after two visits a stream never starts with 11 (av2_guard), and the checker
below tests the condition every time it uses the rule.
From the rules to the machine. Law lists what a machine's two forms must satisfy, one field
per rule, and Law.av, Law.ah turn every abstract visit into a visit of the machine in
form V (and in form W when the guard holds). lean/Law.lean fills in the fields with the theorems of
the table above (law); everything is checked by the kernel.
Step through the first rounds of the rewriting system. Each round puts 1 0 in front of the word
and makes one visit; the highlighted cells are the block the current visit is reading. At the end of every round
the browser compares the word with the machine's tape at the start of the next round.
After k rounds the word begins with about k/2 doublers, so about 2k/2 visits reach the blocks behind
them, and round 161,211 could never be replayed visit by visit. But all the visits that reach one block are
alike, so it is enough to know how many there are. VisitLaw.lean proves what n visits in a row
do (VS n s s', for every n):
000 r under n visits ends as the digit n mod 2, and ⌊n/2⌋ visits reach r (law_Z);100 r ends as the digit (n + 1) mod 2, and ⌈n/2⌉ visits reach r (law_H); the same for
110 r when n ≥ 1 (law_G);1010 r stays 1010, and 2n visits reach r (vs_L, with the guard on r);0 where a block should start takes the first visit to become a 1 (law_0);hvs_Z, hvs_H, hvs_G,
hvs_L, hvs_X).Try a law: the browser makes n visits one by one with the rewriting rules and counts how many of them reach the stream r behind the block (here r starts as blank tape).
The pass. The checker (scan in VisitCheck.lean) carries the number of visits through
the word block by block, in one pass, using these laws: through a doubler n visits become 2n; through a digit n
becomes n/2, rounded down or up depending on the digit, and the digit is set to the parity of n; when the count
reaches 0 the rest of the word is copied unchanged. The counts are huge but simple: each is a power of two minus a
small number, so the checker keeps a count as a pair e, c standing for 2e − c, and doubling is
e + 1, halving is e − 1. scan_sound proves that what the pass returns is what 2e − c
visits of the rewriting system make; hscan_sound proves the same for its search for a halting visit
(sound, not complete: when it is unsure it answers no).
Pick a round and look at the counts. Up to round 40 the browser also makes the round's visits one by one, with the rewriting rules, and compares the number of visits that reach each block with the count the pass carries there.
What is left is a program. round s is one pass of scan over the word 1 0 s
with a single visit (e = c = 0); iter k s makes k rounds and fails if a round fails, as it does when a
positive count meets 1011; and check k s makes k rounds and then asks hscan whether
the next round has a halting visit. halts_of_check_blank (lean/Law.lean, kernel, with the
three standard axioms) says: if check k [true] = true for some k, the machine halts from blank tape. The
word [true] is the word 1 after the 6 steps of start.
So the proof needs the value of one expression, check 161210 [true]. That is about 1011 list
operations, too many for the kernel, so Lean compiles the checker to native code and evaluates it
(native_decide). The run is cut into ten segments, each "k rounds take the word after a rounds to the
word after b rounds", with the words at the boundaries (up to a million cells) written into the proof as numbers
(VisitW*.lean); a kernel-checked lemma, iter_add, chains the segments, and an eleventh
evaluation, last, is the halting round:
| segment | rounds | word after the segment | evaluated by |
|---|---|---|---|
seg1 | 1 to 57,000 | 353,969 cells | native_decide |
seg2 | 57,001 to 80,600 | 500,341 cells | native_decide |
seg3 | 80,601 to 98,700 | 612,769 cells | native_decide |
seg4 | 98,701 to 114,000 | 707,929 cells | native_decide |
seg5 | 114,001 to 127,400 | 790,849 cells | native_decide |
seg6 | 127,401 to 139,600 | 866,761 cells | native_decide |
seg7 | 139,601 to 145,300 | 902,365 cells | native_decide |
seg8 | 145,301 to 150,800 | 936,609 cells | native_decide |
seg9 | 150,801 to 156,100 | 969,541 cells | native_decide |
seg10 | 156,101 to 161,210 | 1,001,253 cells | native_decide |
last | 161,211 | hscan finds a visit that meets 1011 | native_decide |
check_run | all | check 161210 [true] = true | kernel (chaining) |
The checker, the rewriting system and the segment files live in this machine's folder (lean/) and serve its twin 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA0RE_1RE--- as well: they do not depend on the machine, and each machine has its own Visit.lean, Law.lean and Halt.lean. The segments took 10 to 30 minutes each, about 3 hours of computing in all. Each
segment was checked once (13 and 14 November 2026); the whole check was then run again from start to end on a fresh
clone on 14 November 2026 (the commands of check_halt.sh, with the ten segments four at a time, about 40 minutes on four cores) and printed HALT CHECKED. The repository's automatic checks run check.sh (the kernel-only
part) but not check_halt.sh.
The browser can run the beginning of the same computation. The pass below is a byte-array version of
scan; every 1,000 rounds the page also runs the line-by-line port of scan used in the panels
above on the same word and compares the two.
It halts.
Started on a blank tape, the machine 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE--- stops: in round 161,211 a visit meets the block
1011, and the head, in state F, reads a 1. That happens after between 5.9 × 1024,266 and 9.2 × 1024,266 steps (computed, not
proved; see below).
theorem halts_from_blank : HaltsFromBlank := halts_of_check_blank 161210 VisitLaw.Run.check_run
native_decide lean/Halt.lean.
HaltsFromBlank is the machine's own halting from blank tape, defined from its transition table in
lean/Machine.lean.
| link | what it says | checked by |
|---|---|---|
| The machine obeys the rules | For every stream and every left tape, a visit in either form does what the table of rules says, a round is one visit, and the run starts with the word 1 (lean/Visit.lean, generated from the transition table). | Kernel |
| The rules, without the machine | The rewriting system and its count laws (VisitLaw.lean), and the fact that this machine satisfies it (law, lean/Law.lean). | Kernel |
| The program computes the rules | scan and hscan return what the rewriting system gives, so if check k [true] = true the machine halts (VisitCheck.lean, halts_of_check_blank). Axioms: propext, Classical.choice, Quot.sound. | Kernel |
| The run itself | check 161210 [true] = true: ten segments and the halting round, chained by iter_add (VisitRun.lean, VisitSeg*.lean). | native_decide eleven evaluations; the chaining by the kernel |
So everything is checked by Lean's kernel except the evaluation of a checker that is itself proved correct.
That evaluation is by native_decide, compiled code, and the theorem depends on eleven
native_decide axioms, one per evaluation (trust in the Lean compiler; the comment in
Halt.lean names it Lean.ofReduceBool), besides the three standard axioms. The halting
theorem is checked by lean/check_halt.sh, about 3 hours of computing; the repository's automatic checks
run check.sh, the kernel-only part, but not this evaluation.
Elsewhere. The same visit law, in a Coq proof on busycoq's definitions (tools/coq/busycoq/VisitLaw2/,
halts : halts tm c0, Coq 8.20.1, no axioms): the checker of busycoq PR59 extended to two forms of
visit, with the whole run as one vm_compute of about 15 minutes. And the three machines of busycoq PR59
(1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RF_0RC--- and two relatives) obey the same law with one form of visit,
entered one cell further left; PR59 proves in Rocq that they halt in round 161,211. The Lean proof here does not use
PR59, so that both land on the same round is a cross-check (as is the C simulator
holdouts/1RB0LB_0RC0LD_1LD1RE_0LA0RF_1RB0RD_0RB---/c/vis.c, which halts in that round on the PR59
machine). The twin 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA0RE_1RE--- halts in the same round by the same checker run; that is a separate theorem
about a different table, not a consequence of this one.
Between 5.9 × 1024,266 and 9.2 × 1024,266 steps from blank tape to the halt, that is 178.4·280605 to 274.6·280605. A number with 24,267 digits (or 24,268): large, but an ordinary power, not a power tower.
Every visit costs a fixed number of the machine's own steps, apart from its nested visits: 4 or 8 steps for 0 → 1 (entered in C or F), 6 for 100, 8 for 110, 20 for 1010 (the step
numbers in the proofs of lean/Visit.lean, the ones the panel on rounds and visits checks against the
machine). So the step count is the number of visits of each kind times these costs. c/steps.c in
holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---/ repeats the checker's pass for all 161,210 rounds and
adds up the counts per rule: in the completed rounds there are 5.9519·280605 visits each of the
kinds 0 → 1, 100 and 1010 (the largest single count is 280605, in
round 161,210: the count in round r peaks at 2r/2), and at most 2.1164·280605 more of each
in the halting round, which stops part of the way through. The lower bound takes the completed rounds at the
cheaper cost, the upper bound adds the whole halting round at the dearer cost.
The program's word after 161,210 rounds agrees cell for cell with the word in VisitW161210.lean, which
the Lean segments check; the sums are kept as a mantissa and an exponent in floating point (the bounds are widened
by 0.1% for that). Lean's theorems say "after some number of steps" and do not state the numbers. Nothing in these
paragraphs is a Lean theorem.
Nothing for the halting question. Open ends: a Lean proof of the step bounds (they are computed), and a proof of the evaluation inside the kernel (it is about 1011 list operations, too many for kernel reduction).
Before the visit law was found, the run was described as two counters ticking together. That description is kept here: it is how the run looks at the level of the machine, and parts of it are Lean theorems of their own (lean/Rules.lean, lean/Events.lean).
Most of the time the tape is L · engine · R. Each visit of the head to the engine is an event, and every event adds 1 to both counters. In the reference machine of the family (1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RF_0RC---), L is written in blocks of four cells, 0101 for a 1 and 0001 for a 0, lowest digit next to the engine, and R keeps one cell per digit, three cells apart (the cells 9, 12, 15, … right of the head), lowest digit nearest the engine. Nine consecutive events of the reference machine right after its left-end visit at step 1,571,372 (the head in state A on the bold cell):
| step | left of head | head | right of head | L, low bits | R |
|---|---|---|---|---|---|
| 1,571,465 | 0001 0001 0101 0001 | 0 | 0101 00000 000 000 000 000 | 1 | 0 |
| 1,571,529 | 0001 0101 0001 0001 | 0 | 0101 00001 000 000 000 000 | 2 | 1 |
| 1,571,589 | 0001 0101 0101 0001 | 0 | 0101 00000 001 000 000 000 | 3 | 2 |
| 1,571,665 | 0101 0001 0001 0001 | 0 | 0101 00001 001 000 000 000 | 4 | 3 |
| 1,571,733 | 0101 0001 0101 0001 | 0 | 0101 00000 000 001 000 000 | 5 | 4 |
| 1,571,797 | 0101 0101 0001 0001 | 0 | 0101 00001 000 001 000 000 | 6 | 5 |
| 1,571,857 | 0101 0101 0101 0001 | 0 | 0101 00000 001 001 000 000 | 7 | 6 |
| 1,571,945 | 0001 0001 0001 0001 | 0 | 0101 00001 001 001 000 000 | 8 (carry) | 7 |
| 1,572,021 | 0001 0001 0101 0001 | 0 | 0101 00000 000 000 001 000 | 9 | 8 |
(The block of L touching the engine is always 0001; the low bits shown are the next three blocks. The carries are sweeps proved in Lean for every length; in the reference machine r_up and r_down carry the right counter over k ones in 5k + 13 and 3k + 18 steps.)
This machine is a relative in different clothes, the twin of 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA0RE_1RE--- (E1 = 1RB against 0RE): the same clockwork left side (3·2k turns, each count twice, the second time 3 less) and the same tapes (at its left-end visit at step 12,788,128 its tape is exactly the twin's at step 14,008,454).
When L overflows, the carry runs to the left end of the tape, the tape grows by two cells there, and L starts again. The lowest digit of L is the cell where the head turns most often, and the number of its turns between two consecutive left-end extensions follows a strict pattern, without a single exception in the first 1.5·109 steps (ymax.c):
48 96 96 192 192 384 384 … 3·221 3·221 3·222
So the periods of the left side are powers of two in events, each length twice (the counter gains one digit every two periods). The time per event is not constant, because a carry on the right costs more when it crosses junk, so the steps between left-end extensions grow by factors between about 1.35 and 2.05 instead of exactly 2.
The cells that change between events are the digits of the counters: each digit changes about half as often as the one before (chg.c counts, over a whole period, how often each cell changes from one event to the next). On the right, between some digits of R, there are stretches of fixed cells (0101010101 00 1 00 1 00 1 and the like) that the carries cross without changing. They are written when a carry runs into the end of the tape, at irregular event counts, and their layout is what makes the run irregular. How they are produced is not decoded yet.
The machine halts only in state F reading a 1, and F is entered from C1 (0RF) only. After C1, used about 3.1·107 times in 109 steps, the head has read a 0 every time (F0 is used exactly as often); no transition is rare. Halting would need that ordinary step to find a 1. In every run short enough to simulate directly this has not happened. The proof on this page shows that it does happen, in round 161,211.
As in its twin, the tape holds the reference's two counters in other words; here one visit to the engine (A on cell 3) does the left increment and then the right one in a single pass. lean/Events.lean proves the combined visit for every size.
The family (G11-Y): 1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RF_0RC--- (the reference), 1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RB_0RC--- (the same run), 1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD0LC_0RC---, 1RB0LB_0RC0LD_1LD1RE_0LA0RF_1RB0RD_0RB---, 1RB0LB_0RC0LF_1LD1RE_0LA0RB_0RD0RF_0LA--- (all with left-end extensions after 2k events, each twice, to within a few hundred steps of each other); 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA0RE_1RE--- and 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE--- (the same right part, a differently written left counter); and the mirror case 1RB0LB_0RC0LD_1LD1RE_0LA0RB_0RD1RF_1LA---, with the junk on the left.
Left of the start, the visited part of the tape grows like the logarithm of the step count: each new cell costs a roughly constant factor more time, the signature of a counter or of a Collatz-like map whose values are written on the tape (fitted exponent 0.08). Right of the start it grows like the logarithm of the step count: each new cell costs a roughly constant factor more time, the signature of a counter or of a Collatz-like map whose values are written on the tape (fitted exponent 0.071).
After 109 steps the tape spans 248 cells (88 left of the start, 152 right), with a density of 1s of 0.403.
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 | 529,197,137 | B>0 0^3 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0^4 1 0^26 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0^2 1 0 1 0^4 1 0^2 1 0^2 1 0 1 0 1 0^2 1 0 1 0^4 1 0^2 1 0 1 0^4 1 0^5 1 0^2 1 0^2 1 0 1 0^4 1 0^2 1 0^2 1 0^2 1 0 1 0 1 0^2 1 0 1 0^13 1 0 1 0^4 1 0^2 1 |
| left | 732,376,883 | B>0 0^3 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0^2 1 0 1 0^4 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0^2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0^4 1 0^2 1 0 1 0^4 1 0^2 1 0 1 0^7 1 0 1 0^4 1 0^2 1 0 1 0^7 1 0^2 1 0^5 1 0 1 0^4 1 0^2 1 0^2 1 0 1 0^16 1 0 1 0 1 0^2 |
| right | 678,853,833 | 1 0 1^3 0 1^2 0^2 1^3 0 1^3 0 1^3 0 1^3 0 1^2 0^2 1^2 0^2 1^3 0 1^2 0^2 1^2 0^2 1^3 0 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0 1^3 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^3 0 1^2 0^2 1^2 0^2 1^3 0 1^2 0 1^2 0 1^3 0 1^2 0 1^2 0 1^3 0 1^2 0 1^2 0 1^3 0 1^2 0 1^2 0 1^3 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^3 0 1^2 0 1^2 0 1^2 0 1^3 0 1^2 0 1 |
| right | 729,649,043 | 1 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^3 0 1^2 0^2 1^2 0^2 1^3 0 1^2 0^2 1^2 0^2 1^3 0 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0^2 1^2 0 1^3 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^3 0 1^2 0^2 1^2 0^2 1^3 0 1^2 0 1^2 0 1^3 0 1^2 0 1^2 0 1^3 0 1^2 0 1^2 0 1^3 0 1^2 0 1^2 0 1^3 0 1^2 0 1^2 0 1^2 0 1^2 0 1^2 0 1^3 0 1^2 0 1^2 0 1^2 0 1^3 0 1^2 0 1^2 |
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.
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 (F1); 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.
lean/Rules.lean (generated by py/rules.py)The shift rules the machine uses in its run (every sweep met when the symbolic simulator runs from many configurations of the run), each for every number of copies.
lean/Events.lean (generated by py/events.py)One event (A on cell 3, phase 1) is the left increment (carry over n ones, digits 0110/0111) followed by the right increment in one pass: on a lowest 0 (18n+70 steps), over k+1 ones (6k+18n+76), across one junk unit (18n+110, 18n+116), across j units then k+1 ones (34j+6k+18n+82). 5 theorems.
V_0, V_100, V_110, V_1010, V_1011_halts, W_*, round, round_halts, start, lean/Visit.lean (generated by py/visit2.py)A visit (the head on a 0 with a 0 on its left and a stream s on its right, in state C or F; it returns in state A two cells further left) rewrites the stream by 0 s → 1 s, 100 s → 000 v(s), 110 s → 000 v(s), 1010 s → 1010 v(v(s)), and halts the machine on 1011 s; for every stream and every left tape. Both forms obey the same rules. The run is a sequence of rounds 0^inf A> 1 0 0 S → 0^inf A> 1 0 0 v(1 0 S), starting after 6 steps with S = 1 0^inf.
AV, AH, Law.av, Law.ah, av2_guard, law_Z, law_H, law_G, vs_L, hvs_*, VisitLaw.leanThe four rules and the halting pattern as inductive relations on streams, with no machine in them; the 1010 rule is guarded (the stream behind must not start with 11), and after two visits a stream never starts with 11. Under n visits, 000 r and 100 r are binary digits that pass every second visit on, and 1010 r passes 2n visits on; likewise for "one of the first n visits halts".
scan_sound, hscan_sound, round_sound, VisitCheck.leanscan carries a count of visits, kept as the pair e, c for 2e − c, through a finite word in one pass; hscan looks for a halting visit. Both are proved against the abstract system.
law, halts_of_check_blank, lean/Law.lean; halts_of_check, VisitCheck.leanThis machine satisfies the law, so for every k: if the checker runs k rounds from the word 1 and then finds a halting visit in the next round, the machine halts from blank tape. Axioms: propext, Classical.choice, Quot.sound.
halts_from_blank, lean/Halt.lean; check_run, VisitRun.lean, VisitSeg1.lean to VisitSeg10.lean; run with lean/check_halt.shcheck 161210 [true] = true: rounds 1 to 161,210 use the four rewriting rules only, round 161,211 meets 1011. Evaluated with the checker compiled to native code, in ten segments chained by a kernel-checked lemma (about 3 hours of computing in all; the word grows to 1,001,253 cells). With the claim above: the machine halts. Besides the three standard axioms the theorem depends on eleven native_decide axioms, one per evaluation (trust in the Lean compiler). The number of steps is bounded separately (computed). Each segment was checked on 13 and 14 November 2026, and the whole check was run again from start to end on 14 November 2026 (HALT CHECKED). The repository's automatic checks cover the kernel-only part, not this evaluation.
holdouts/triage.jsonThe C simulator tools/c/triage.c runs 109 steps without a halt; at the end 248 cells have been visited and 100 of them hold a 1.
holdouts/1RB---_0LC0RB_1RA1LD_0RD1LE_1LF0LA_1LB0LE/c/longrun.cA direct run of 1011 steps (longrun.c, the simulator of tools/c/tm.h) without a halt.
holdouts/1RB---_0LC0RB_1RA1LD_0RD1LE_1LF0LA_1LB0LE/c/ymax.cBetween consecutive left-end extensions the busiest cell turns 3·2k times, each count twice (48, 96, 96, ..., 3·222), in the first 1.5·109 steps.
python3 py/events.py --coverage 100000000 (with c/evdump.c of 1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RB_0RC---)In the first 108 steps (513,702 events) 90.5% of the events are instances of these theorems (r0 256,841; r1 92,325; j10 75,989; j110 37,990; jk 1,733); the other 48,824 are carries over other junk layouts and the moments around the ends.
holdouts/1RB0LB_0RC0LD_1LD1RE_0LA0RF_1RB0RD_0RB---/c/vis.cThe three machines of busycoq PR59 (1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RF_0RC--- and two relatives) obey the same law with one form of visit, and PR59 proves in Rocq that they halt in round 161,211. The proof here does not use PR59; our C simulator of the law (vis.c) also halts in that round on the PR59 machine. The twin 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA0RE_1RE--- has its own theorem: machines with related tables are not claimed to halt together.
c/steps.c in holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---/Computed, not proved: the machine halts after between 5.9 × 1024,266 and 9.2 × 1024,266 steps (178.4·280605 to 274.6·280605). Every visit costs a fixed number of steps of its own: 4 or 8 steps for 0 → 1 (entered in C or F), 6 for 100, 8 for 110, 20 for 1010. A C program repeats the checker's pass for all 161,210 rounds and adds up the visits per rule (5.9519·280605 of each main kind in the completed rounds, at most 2.1164·280605 more in the halting round). Its final word agrees cell for cell with the word the Lean segments check; the sums are in floating point, and the bounds are widened by 0.1% for that.
tools/py/bbtools/triage.pyLeft of the start, the visited part of the tape grows like the logarithm of the step count: each new cell costs a roughly constant factor more time, the signature of a counter or of a Collatz-like map whose values are written on the tape (fitted exponent 0.08). Right of the start it grows like the logarithm of the step count: each new cell costs a roughly constant factor more time, the signature of a counter or of a Collatz-like map whose values are written on the tape (fitted exponent 0.071).
README.mdRead off the run: the counters on the two sides of the engine both go up by 1 at every visit of the head to the engine, one of them with fixed junk stretches between some digits; the junk is written when a carry reaches the end of the tape.
holdouts/related.json, written by holdouts/related.py compute (tools/c/cfgmatch.c, tools/c/lockstep.c)The same tapes at another pace, whatever the states, as 1 other holdout (listed on the explainer page).
. /etc/profile.d/lean.sh # after scripts/setup-lean.sh
holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---/lean/check.sh
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE--- 1000000000
python3 holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---/py/visit2.py 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE--- H60498 /dev/stdout 2>/dev/null | diff - holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---/lean/Visit.lean
holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---/lean/check_halt.sh # the halting theorem: compiles the checker, then ten native_decide segments, about 3 hours