Busy Beaver Explorer / holdouts / 1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE--- / explained

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

Does this machine ever halt?

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.

native_decidehaltshalts_from_blank, proved in Lean (kernel + native_decide for the checker run).
KernelVisit lawThe machine as a rewriting system on streams; the checker and its correctness proof.
native_decideround 161,211The first round in which a visit meets 1011.
Computed~1024,266 stepsBetween 5.9 × 1024,266 and 9.2 × 1024,266 (computed).
Also proved in CoqA second proof assistant checks the same result: 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.
Community labelIn the community's BB(6) tracker the machine's class is Shift-overflow counter. 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 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 >.

statereads 0reads 1
A1 R B0 L B
B0 R C0 L E
C1 R D0 R F
D1 L B1 R B
E0 L A1 R B
F1 R Ehalt
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.

Five levels

From six states to one computation

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

One moment, five descriptions

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.

start of round 12
1 · Machine
10head, state Aunder a doubler 1010under a digit
2 · Round
3 · Rewriting
4 · Counting pass
5 · Checker
The word S is drawn in blocks as the next round's pass reads it: blue blocks 1010 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.
Level 1 to level 2

Rounds and visits

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 beginsafter the visitform V (entered in state C)form W (entered in state F)
0 s1 sV_0: 4 stepsW_0: 8 steps
100 s000 v(s)V_100: 3 steps, then V, 3 stepsW_100: 3 steps, then V, 3 steps
110 s000 v(s)V_110: 5 steps, then V, 3 stepsW_110: 5 steps, then V, 3 steps
1010 s1010 v(v(s))V_1010: 4 steps, then W, 2 steps, then V, 14 stepsW_1010: 4 steps, then W, 2 steps, then V, 14 steps
1011 sthe machine haltsV_1011_halts: after 4 steps, F reads a 1W_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.

round 6
1heada visit begins, state C (form V)a visit begins, state F (form W)
Level 2 to level 3

The same rules without 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 beginsone visit makesrule
0 s1 sAV.z
100 r000, and one visit to rAV.h
110 r000, and one visit to rAV.g
1010 r1010, and two visits to r, if r does not start with 11AV.l
1011 rthe visit haltsAH.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.

Level 3 to level 4

Counting visits instead of making them

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);
  • a 0 where a block should start takes the first visit to become a 1 (law_0);
  • and the same laws for "one of the first n visits halts" (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).

n = 13

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.

round 40
Level 4 to level 5

161,210 rounds, then the trap

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:

segmentroundsword after the segmentevaluated by
seg11 to 57,000353,969 cellsnative_decide
seg257,001 to 80,600500,341 cellsnative_decide
seg380,601 to 98,700612,769 cellsnative_decide
seg498,701 to 114,000707,929 cellsnative_decide
seg5114,001 to 127,400790,849 cellsnative_decide
seg6127,401 to 139,600866,761 cellsnative_decide
seg7139,601 to 145,300902,365 cellsnative_decide
seg8145,301 to 150,800936,609 cellsnative_decide
seg9150,801 to 156,100969,541 cellsnative_decide
seg10156,101 to 161,2101,001,253 cellsnative_decide
last161,211hscan finds a visit that meets 1011native_decide
check_runallcheck 161210 [true] = truekernel (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.

After k rounds (across): the length of the word (left scale, cells), and the exponent e of the largest count 2e − c that the pass carries in the next round (right scale). Each point is every 50th round.
The bottom line

It halts

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.

What it rests on

linkwhat it sayschecked by
The machine obeys the rulesFor 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 machineThe 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 rulesscan 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 itselfcheck 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.

How many steps Computed

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.

Still open

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 proof

Two counters and an engine

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

Two counters and an engine

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

stepleft of headheadright of headL, low bitsR
1,571,4650001 0001 0101 000100101 00000 000 000 000 00010
1,571,5290001 0101 0001 000100101 00001 000 000 000 00021
1,571,5890001 0101 0101 000100101 00000 001 000 000 00032
1,571,6650101 0001 0001 000100101 00001 001 000 000 00043
1,571,7330101 0001 0101 000100101 00000 000 001 000 00054
1,571,7970101 0101 0001 000100101 00001 000 001 000 00065
1,571,8570101 0101 0101 000100101 00000 001 001 000 00076
1,571,9450001 0001 0001 000100101 00001 001 001 000 0008 (carry)7
1,572,0210001 0001 0101 000100101 00000 000 000 001 00098

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

The left side is clockwork

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.

A counter with junk between its digits

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

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.

The increments, proved for every size

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.

Eight machines, one mechanism

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.

First look

The shape of the run

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

2^42^82^122^162^202^242^282^02^42^8■ left of start ■ right of start (steps across, cells up)

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:

sidesteptape
left529,197,137B>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
left732,376,883B>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
right678,853,8331 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
right729,649,0431 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.

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.

1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE--- (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 (F1); 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.

Kernel
lean/Rules.lean (generated by py/rules.py)
The sweeps of the run

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.

Kernel
lean/Events.lean (generated by py/events.py)
Both counters' increments, for all sizes

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.

Kernel
V_0, V_100, V_110, V_1010, V_1011_halts, W_*, round, round_halts, start, lean/Visit.lean (generated by py/visit2.py)
The visit law, in two forms

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.

Kernel
AV, AH, Law.av, Law.ah, av2_guard, law_Z, law_H, law_G, vs_L, hvs_*, VisitLaw.lean
The abstract visit law and its count laws

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

Kernel
scan_sound, hscan_sound, round_sound, VisitCheck.lean
A checker for the visit law, proved correct

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

Kernel
law, halts_of_check_blank, lean/Law.lean; halts_of_check, VisitCheck.lean
If the checker accepts, the machine halts

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

native_decide
halts_from_blank, lean/Halt.lean; check_run, VisitRun.lean, VisitSeg1.lean to VisitSeg10.lean; run with lean/check_halt.sh
The machine halts from blank tape

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

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 248 cells have been visited and 100 of them hold a 1.

Computed
holdouts/1RB---_0LC0RB_1RA1LD_0RD1LE_1LF0LA_1LB0LE/c/longrun.c
No halt in the first 1011 steps

A direct run of 1011 steps (longrun.c, the simulator of tools/c/tm.h) without a halt.

Computed
holdouts/1RB---_0LC0RB_1RA1LD_0RD1LE_1LF0LA_1LB0LE/c/ymax.c
The left side is clockwork

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

Computed
python3 py/events.py --coverage 100000000 (with c/evdump.c of 1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RB_0RC---)
How much of the run the increments cover

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.

Computed
busycoq PR59; holdouts/1RB0LB_0RC0LD_1LD1RE_0LA0RF_1RB0RD_0RB---/c/vis.c
The same round as the PR59 machines

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

Computed
c/steps.c in holdouts/1RB0LB_0RC0LE_1RD0RF_1LB1RB_0LA1RB_1RE---/
Between 5.9 × 1024,266 and 9.2 × 1024,266 steps

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.

Heuristic
tools/py/bbtools/triage.py
Growth shape: exp/exp

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

Heuristic
README.md
Two counters of the same events

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

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

The same tapes at another pace, whatever the states, as 1 other holdout (listed on the explainer page).

Check it yourself

Commands

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