Busy Beaver Explorer / holdouts / 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC / explained

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

Does this machine ever halt?

1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC

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: the tape is a list of counts, the first one counts down by 3 on every trip, the rest of the list cycles through one of four patterns, and every way this can go has been checked symbolically. This page runs it in your browser and shows the counters.

native_decidenever haltsProved in Lean; the 62 round trips by the kernel, the start and the 62 epoch ends by native_decide.
Computed109 stepsNo halt in the C simulator; 39,660 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: H36670.nonhalt : ~ halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in tools/coq/busycoq/H36670. Coq 8.18 compiles it and Print Assumptions reports no axioms; the build log is next to the files. A shorter proof of the same theorem (a 668-line checker for tapes with two blocks of unknown length and a 58-line file with four seed tapes; Coq 8.20.1 checks it in about 25 seconds) is on a branch of our fork of busycoq, ready to be proposed upstream: bb6-nonhalt-1RB0LF_1LC0LA_1RA0RD_HHH1RE_1LA1RC_0LB0RC.
Community labelIn the community's BB(6) tracker the machine's class is Bell-like. These are labels read off the run by others, not results.
Kernel proved in Lean, checked by the kernel only
native_decide proved in Lean, one evaluation trusts the compiler
Computed C or Python in the repository, tested but not proved
Heuristic evidence and estimates
Open not known
The machine

6 states, two symbols, 1 halting transition

Each entry says what to write, which way to move and which state to enter. The machine starts in A on a blank tape (all 0s).

The machine stops when it is in D reading 0. D is entered only from C1 (writes 0, moves R): C>1 0. So a halt is the moment this pattern appears, with the head on the cell after >.

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

The question "does this machine halt?" is answered here by walking down a ladder of five descriptions of the same run. Each level forgets detail that the level above keeps and has its own, longer unit of time. Each step down is a Lean theorem saying that one move at the lower level is a real run of the machine, at least one step long, from one configuration to the next. So a run that goes on forever at the bottom level is a run of the machine that goes on forever: the machine never halts. The badge on each card says what Lean used to check that step (Kernel: Lean's small trusted core; native_decide: a compiled program whose answer Lean takes on trust).

One moment, every level

Pick a moment of the run: the n-th time, counted from step 1,277,431, that the tape is one of the 62 templates. The browser runs the real machine from blank tape to that moment, cell by cell, and reads its tape. It also runs the shift-rule simulator of level 2 from blank tape, and the tables of the proof (levels 3 to 5) from the first template. The rows show the same instant at each level, and the check marks say that the computations agree.

moment 39
Jump to:
1 · Machine
first stretch (01)asecond stretch (01)bthe tailthe head, at the left edge
2 · List
3 · Template
4 · Epoch
5 · Potential
Moments 0 to 2,764 cover the first 3·108 steps and four epoch ends. The machine is simulated step by step; going far forward takes the browser a few seconds (the work is kept, so going back is instant). Before step 1,277,431 the tape is never one of the templates: that stretch is the setup, shown in its own section below.
Level 1

The machine, and the one way it could halt

The table has one missing entry: D reading a 0. That is the only way to halt (step_none_iff, Kernel). The only transition into D is C reading a 1 (C writes 0, moves right, enters D), so a halt happens exactly when the head in state C sees 1 0. Lean also proves the short ways there (halt_C, halt_E, halt_F, halt_D in lean/Rules.lean, Kernel): C>1 0 halts after one step, E>1 1 0 and F>1 1 0 after two, D>1 1 1 0 after three.

The proof never looks for this pattern 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". In the first 2·108 steps the machine is in state D 22,202,037 times, every time on a 1 (c/visits.c, Computed).

Press Step to see the halting pattern play out on a made-up tape.

From cells to a list of numbers

Watch the machine for a while (the simulator above) and most of the tape turns out to be long stretches of 0 1 0 1 0 1 …. Stop it at the moments when the head, in state B, stands at the left end of the written tape on a 0: the left-end moments. At those moments the tape reads

B>00(01) × a000(01) × b000(01) × c…

a list of numbers a, b, c, … written as stretches of 01, separated by short words such as 000, 00001000 or 11. The machine is a little computer working on this list. The first number a counts down, the second number b grows, and the short tail after them goes round in a cycle. The panel steps through the left-end moments of the run from blank tape and reads each tape as a list (two or more 01s in a row become a number, as in py/regimes.py).

The cells, from the head:
The same cells as a list:

The first moment at which the list has the exact shape of one of the proof's 62 templates is step 1,277,431. The button runs the machine there from blank tape and compares.

Level 1 to level 2

Crossing a stretch in one move

Between left-end moments the head sweeps across the long stretches. A stretch of a million cells would take a million steps to simulate, but what happens to it is simple, and Lean proves it once for every length:

  • Going right (sweep_right): B, with a 1 just behind it, turns each block 010101 into 011001 and comes out the other side, again in state B, after exactly 14 steps per block.
  • Going left (sweep_left): C, with 110 ahead of it, turns each 011001 back into 010101, 22 steps per block.

Each is proved by running one block for real (rfl, so Lean's kernel computes the 14 or 22 steps) and then a general lemma, cross_r or cross_l, that says: if one copy takes the head through in the same state, n copies do too, in n times the steps. Kernel

Any number of blocks. Type a number of blocks n. The browser runs the plain machine on the rule's starting tape until the head comes out the far side in the starting state, and compares the step count and the tape with what the theorem says.

Level 2: the tape as a list, moved by moves

A round trip from a template is a claim about infinitely many tapes, one for each size. Lean cannot simulate them one by one. Instead it runs the machine symbolically: the tape is a list of tokens, single cells and stretches (01)n whose count n is a formula such as 3k + 7. The checker steps the machine on cells it can see. When the head meets a stretch, it tries one copy on its own (as in the panel above) and, if the head comes out the far side in the same state, crosses the whole stretch in one move. If it would need to know whether a count is 0 or not, it gives up and the check fails.

The checker is a program, auto in lean/SymCheck.lean, and it comes with a theorem, auto_reach, proved once by the kernel: if auto answers true for a start and a target, then for every value of the variables the real machine goes from the start to the target in at least one step. Kernel That is the step from level 1 to level 2: every move at level 2 is a run of the machine.

This page has its own small version of the same idea, the shift-rule simulator: the tape is a list of tokens with ordinary numbers as counts, a whole stretch is crossed in one move whenever one copy tried on its own takes the head through in the same state, and at each left-end moment the list is written in normal form again. It is not the Lean program, and it works with numbers rather than formulas, but it makes about as many moves (for example 140,054 from blank tape to step 1,277,431, where Lean's checker makes about 148,000). The one-moment panel checks it against the plain machine at every moment; the next sections use it to run round trips and epoch ends of any size.

Level 2 to level 3

One round trip, for any size

From one left-end moment to the next is a round trip: the head sweeps right to the far end of the tape and back. What it does to the list depends on the short tail, which takes one of 62 shapes (the 62 templates, named R0_0 … R3_8, see the next section). In each template the first two numbers are written with two free variables:

a = 3k + 4    b = 3j + β   (β between 6 and 8, fixed per template)

Lean proves, for each template t and for every k and j: a round trip takes template t with numbers (k + 1, j) to the next template nxt t with numbers (k, j + dj), where dj is a small constant listed for each template. So a drops by 3 and b grows by 3·dj. These are the 62 theorems round_0 … round_61, each a run of the symbolic checker of 200 to 2,500 moves, evaluated by the kernel. Kernel That is the step from level 2 to level 3: one round trip at level 3 is one run of the checker, so one run of the machine.

A small one, cell by cell. Pick a template and small values of k and j, and run one round trip on the plain machine. The diagram shows the tape (rows are moments, time going down; dark = 1) and the path of the head (orange line): out to the right end over the stretches, and back. The check compares the tape after the trip with what the theorem predicts, cell by cell.

Before:
After:

Any size, move by move. The same round trip run by the shift-rule simulator of level 2, with k and j as large as you like (up to 1012). The log lists its moves: runs of single steps, and whole stretches crossed at once by a shift rule. The count of moves does not depend on the size; the count of steps does. The result is compared with the theorem's prediction, and, when the trip is under 3·107 steps, with the plain machine as well.

Before:
After:
Level 3

62 templates in four cycles

Follow the templates from one round trip to the next (nxt in lean/Tables.lean) and they go round in cycles. There are four cycles, called regimes R0 to R3, with 15, 22, 16 and 9 templates. After one full lap of a regime the tail is exactly as it was, a has dropped by 45, 66, 48 or 27 (3 per trip), and b has grown by 99, 141, 99 or 57. Click a template in the rings to see its shape; the button runs the selected regime's whole lap on the machine.

Template R0_0 as Lean states it (dashed bars: counts with variables):
One lap of the selected regime, as observed in the run (a and b are concrete numbers here):
Level 3 to level 4

When the countdown runs out: from one epoch to the next

Round trips need k ≥ 1. When k reaches 0 (a = 4) the countdown cannot go on. What happens next has three parts, and Lean checks them together as one end case per template. We call the stretch between two such events an epoch.

  1. The reset (three returns to the left end). The last 4 copies of 01 in a are used up and the short word in front of b is rewritten. The old b ends up first in the list, with a few more copies. In the example below the new a is 724 + 6 = 730.
  2. The transient (up to about 145 round trips). Each trip still takes 3 from the new a, as before. But the tail of the list is in disorder after the reset, so it does not yet follow any of the 62 templates. The new b starts small and grows. Now and then two pieces of the tail merge.
  3. Settling. The tail falls into one of the four regimes, and the tape is a template again: endT t, with a new k that is large and a new j that is small.

Lean proves, for each template t and every j: from template t with numbers (0, j + 200), the machine reaches the template endT t with numbers (j + endC1, endC2). These are the 62 end cases, checked together as ends_ok: runs of the symbolic checker of 4,200 to 127,000 moves each, 2.5 million in all, evaluated by compiled code because the kernel runs out of memory on runs this long. native_decide That is the step from level 3 to level 4: an epoch is k round trips followed by one end case, and at level 4 the whole epoch is one move, from (t, k, j) to (endT t′, …) where t′ is the template reached at k = 0.

The first epoch end of the proof, in the real run. At step 1,908,405 the tape is template R1_10 with k = 0 and j = 239 (a = 4, b = 724). The proof's end case for R1_10 says the run reaches R1_16 with k = (239 − 200) + 81 = 120 and j = 259. Below, the browser runs the machine through it, from that step to step 4,054,968. The slider moves through every moment at which the head is back at the left end. The chart shows a (blue) and b (green) at each of those moments.

The reset, moment by moment. The four left-end moments from step 1,908,405 to step 1,946,128, as lists. Blue is the first count, green the second.

Why "j + 200". During the transient the new a, which comes from the old b, still loses 3 every round trip. It must not run out before the tail has settled, or the end case would be a different computation. The symbolic checker cannot ask whether a count is zero, so it needs a guarantee up front. The end cases are stated for an old b of at least 3 · 200 + β copies (j ≥ 200). The longest transient takes under 150 round trips, so it uses fewer than 450 of those copies. The potential (level 5) shows that j is always at least 200 when an epoch ends.

The first button runs all 62 end cases on the plain machine at the smallest size the proof allows (j = 200 exactly), and checks that each reaches its predicted template cell for cell. The second runs them on the shift-rule simulator at any j you choose. These are independent checks of the claims behind ends_ok, at one size each; Lean's check covers every size. The chart shows how many left-end moments each end case takes.

Epoch after epoch. In a round trip b grows by roughly 2.2 for every 1 that a loses, and at the reset b becomes the new a. So each epoch is about twice as long as the one before. The chart shows the first number a at the start of each epoch, read off the certificate's tables starting from the template the run reaches at step 1,277,431 (log scale).

Into level 4

Before the first template: the setup

The proof starts at step 1,277,431, not at step 0. The first 1,277,431 steps are the setup, and Lean checks them as one long computation: start_ok runs the symbolic checker from the blank tape to template R1_16 with k = 38, j = 163. The sweep rules let it cross long stretches in one move, so that takes about 148,000 symbolic moves. native_decide This is how the run enters level 4: from there on it is a sequence of templates.

What happens in the setup? The machine does the same things as later, at small sizes. From the start the left-end list counts down a by 3 per round trip, and resets when a runs out. So the setup is a series of short epochs (the table below lists their resets), each roughly twice as long as the one before. In the early ones the numbers are too small for the tail to settle into a regime. The first time the tape fits one of the 62 templates is step 1,277,431, in the epoch that began at step 503,461. That is where the proof takes over.

The chart shows a (blue) and b (green) at every left-end moment from the blank tape to step 4,054,968, computed in your browser (log scale; dots mark the resets). Use the slider to see the list at each moment.

The table lists each reset of the setup and of the first proof epoch: the step, b at the last moment before the reset, and the new a just after it. The new a is the old b plus some copies: 6 at the first reset of the proof, more during the setup, where pieces of the tail also merge into it.

Level 4 to level 5

Why there is always enough room

The end cases need j ≥ 200 at the moment k reaches 0. The proof gets this from a potential, a single number for each good tape:

Φ = j + 2k + pot(t)

where pot(t) is a number between 0 and 15 listed for each template (potL in lean/Tables.lean). Two facts about the tables, both checked by Lean's kernel (tables_ok) Kernel:

in a round trip
k drops by 1 (Φ loses 2), j grows by dj, and pot changes; the tables satisfy pot(t) + 2 ≤ pot(nxt t) + dj(t), so Φ never decreases.
after an epoch end
the new values give Φ ≥ endC2 + 2·endC1 + pot(endT) ≥ 215 for every template.

So Φ ≥ 215 on every good tape. At an epoch end k = 0, so j ≥ 215 − pot(t) ≥ 215 − 15 = 200, exactly what the end cases need. That is the last step down, from level 4 to level 5: the whole run is now one number that never falls below 215. The table below runs the same checks as tables_ok in your browser, on the numbers of lean/Tables.lean.

The chart follows Φ along the first 3,000 good tapes of the run, from the tables (log scale; the dashed line is 215). Move the slider to read each one.

The bottom line

It never halts

It never halts. Started on a blank tape, the machine 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC runs for ever.

The Lean theorem is H36670.nonhalting : ¬ HaltsFromBlank in lean/Cert.lean, where HaltsFromBlank is defined from the machine's transition table in lean/Machine.lean.

What it rests on. Lean's kernel checks everything except two evaluations: start_ok (blank tape to the first template, about 148,000 symbolic moves) and ends_ok (the 62 end cases, 2.5 million moves), which are run as compiled code with native_decide because the kernel runs out of memory (over 6 GB) on runs this long. #print axioms H36670.nonhalting lists propext and Quot.sound, two standard axioms of Lean's logic, and the two native_decide axioms, one for each of those evaluations. Nothing about the run is assumed: a wrong number in the tables would only make a check answer false. native_decide

The argument in one picture

The proof is an invariant: a description of a set of tapes, called good, with three properties.

  1. The run reaches a good tape. From the blank tape, after 1,277,431 steps, the tape is good.
  2. A good tape always leads to another good tape. From any good tape the machine makes at least one step, without halting, and arrives at a good tape again.
  3. So the machine never halts. Repeating the second property forever gives runs of every length, and a machine that halts has runs of only bounded length.

What makes a tape "good" is levels 3 to 5 above: it is one of the 62 templates, a list of numbers written on the tape in a fixed pattern, with two of the numbers free (k and j) and the size condition Φ ≥ 215 on them. The second property then splits into finitely many checks, one per template and case.

Blank tapestate A, all 0s Start run1,277,431 steps totemplate R1_16, k=38, j=163 Good tapeone of 62 templateswith j + 2k + pot ≥ 215 Round trip (k ≥ 1)62 cases, kernel Epoch end (k = 0)62 cases, native_decide Symbolic checkerproved to agree withthe machine (kernel) Potential tableskeep the size condition(kernel) Never haltsruns of every lengthnonhalting
Kernel green boxes
native_decide blue boxes

Who checks the computations

Each round trip and end case becomes a computation: "does auto answer true on this input?". Who runs that computation is the one place where the proof uses two levels of trust:

decide +kernel
Lean's kernel evaluates the program itself, step by step. This is the most trusted way, and it is used for the 62 round trips and the potential tables.
native_decide
Lean compiles the program to machine code and runs it. The kernel then accepts the answer as an axiom. Used for the start (about 148,000 symbolic moves) and the 62 end cases (2.5 million in all), because the kernel ran out of memory (over 6 GB) on runs that long.

Every piece, and what it rests on

Every piece of the proof, and what it rests on. A wrong number anywhere in the tables cannot make the proof pass: it would only make one of the checks answer false.

PieceWhat it saysChecked by
Machine.leanthe machine's table and what a step is (generated from the machine's name)Kernel
sweep_right, sweep_leftthe two shift rules, for any number of blocksKernel
auto_reachthe symbolic checker agrees with the real machineKernel
round_0 … round_61the 62 round trips, every k and jKernel
tables_okthe potential never lets j fall below 200 at an epoch endKernel
start_okblank tape reaches template R1_16 at (38, 163)native_decide
ends_okthe 62 epoch ends, every jnative_decide
nonhaltingglues the pieces together (the induction of the first picture)Kernel

#print axioms H36670.nonhalting lists propext and Quot.sound (two standard axioms of Lean's logic) and exactly two native_decide axioms, one for start_ok and one for ends_ok. Trusting them means trusting that Lean's compiler and runtime evaluated the checker correctly on those inputs. The checker's own logic is not trusted: auto_reach is a kernel proof.

Independent checks of the two native_decide pieces Computed. These are separate from Lean and do not replace a kernel proof, but they test the same claims by a different route, plain simulation with a small C program:

  • The start: the plain simulation reaches exactly template R1_16 at (38, 163) at step 1,277,431. You can repeat it in the level 1 section; your browser does the same computation, and the one-moment panel at the top runs both the plain machine and the shift-rule simulator past it.
  • The 62 end cases: each one was run concretely at j = 0 (b with exactly 3·200 + β copies) and at j = 13, and each reached exactly the predicted template and numbers, taking up to 2.6 million steps. The level 4 section repeats this in your browser, at j = 200 on the plain machine and at any j on the shift-rule simulator.
  • The whole chain: the sequence of templates the tables predict was matched, in order, against the plain run from blank tape: 2,765 consecutive good tapes up to step 3·108, including 4 epoch ends. The one-moment panel at the top of the page repeats this match in your browser, one moment at a time.

A proof using only the kernel needs the long runs cut into pieces of a few thousand symbolic moves, with each intermediate tape written out (about 900 pieces). That work was started and is not finished.

The last lines of the proof, in words
Good c
c is template t with numbers k, j (t one of the 62), and j + 2k + pot(t) ≥ 215.
start_good
some run from the blank tape ends at a good tape (from start_ok).
good_step
from a good tape, at least one step leads to a good tape. If k ≥ 1 it uses that template's round trip, if k = 0 its end case, and the tables to show the new tape is good again.
nonhalting_of
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 (not_halts_of_forall, forall_of_unbounded), and the machine does not halt.
nonhalting
¬ HaltsFromBlank, from nonhalting_of and ends_ok.

The full statements are in lean/Cert.lean; lean/check.sh checks everything in about 5 minutes on one core.

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

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 39,660 cells (8,102 left of the start, 19,554 right), with a density of 1s of 0.5.

The tape (run-length coded, 1^5 is five 1s, C>0 the head in state C on a 0) at some of the last moments the head reached a new cell, cut to 400 characters:

sidesteptape
left957,202,740B>0 0^2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
left973,114,624B>0 0^2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
left988,968,318B>0 0^2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
right961,904,0240 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1
right978,000,3470 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1
right993,834,8580 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1 0 1^2 0^2 1

These are measurements of one bounded run, sorted by tools/py/bbtools/triage.py; the macro structure behind them is described above.

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.

1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC (this machine)

What is known

Every result, by what it rests on

Status as of 8 November 2026. The same list as the proof-status page, built from the same file.

Kernel
step_none_iff, lean/Blank.lean
The halting configurations

The machine stops exactly when it reads the symbol of a halting transition (D0); the generated statement covers every configuration.

Kernel
blank_runs_kernel, lean/Blank.lean
No halt in the first 10,000 steps

The list simulator of the shared library, proved to agree with the machine's semantics, runs 10,000 steps from blank tape without a halt, evaluated by Lean's kernel.

native_decide
blank_runs_native, lean/Blank.lean
No halt in the first 107 steps

The same run, evaluated by compiled code.

Computed
holdouts/triage.json
No halt in the first 109 steps

The C simulator tools/c/triage.c runs 109 steps without a halt; at the end 39,660 cells have been visited and 19,822 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.497). 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.507).

Kernel
sweep_right, sweep_left, lean/Rules.lean
Shift rules

B with a 1 behind it turns each 010101 into 011001 going right (14 steps a copy); C with 110 ahead turns each 011001 back into 010101 going left (22 steps a copy).

Kernel
halt_C, halt_E, halt_F, halt_D, lean/Rules.lean
The halting situations

C>1 0 halts after one step, E>1 1 0 and F>1 1 0 after two, D>1 1 1 0 after three.

Kernel
auto_reach, lean/SymCheck.lean
A verified symbolic checker

lean/SymCheck.lean: configurations whose tape is a list of cells and runs wn with n linear in some variables; auto finds the moves itself (a run crossed by a shift rule found on the spot, else one step) and compares normal forms at the left end. auto_reach proves that a successful check means the machine makes that run, for every value of the variables.

Kernel
round_0 … round_61, tables_ok, lean/Cert.lean
The 62 round trips

Each phase template B> 00 (01)3k+4 000 (01)3j+β rest at [k+1, j] reaches the next phase at [k, j + dj] (200 to 2,500 symbolic moves each), evaluated by the kernel. The tables also show that j + 2k + pot never decreases in a round and is at least 215 after an epoch.

native_decide
ends_ok, lean/Cert.lean
The 62 ends of an epoch

Each template at [0, j+200] reaches a template again, with the old second count as the new first (4,200 to 127,000 symbolic moves each, 2.5 million in all), evaluated by compiled code; the kernel runs out of memory on runs this long.

native_decide
start_ok, lean/Cert.lean
The start

From blank tape the machine reaches template 31 (pattern R1, phase 16) with first count 118 and second 496, at step 1,277,431 (147,895 symbolic moves).

native_decide
nonhalting, lean/Cert.lean
It does not halt from blank tape

The invariant “at a template with j + 2k + pot ≥ 215” holds at the start and is restored after a round or an end, each taking at least one step, so the run is defined for every length. #print axioms lists propext, Quot.sound and the two native_decide axioms.

Heuristic
py/regimes.py, py/endcases.py
Four regimes, growing epochs

How the templates were found: along the run, the list at the left end settles each epoch into one of four periodic patterns of period 15, 22, 16 or 9 round trips, in which the first count drops by 3 per trip and the second grows by 99, 141, 99 or 57 per period. Concrete simulations from every phase and residue return to a pattern.

Computed
c/visits.c
D never reads a 0 in 2·108 steps

In the first 2·108 steps the machine is in state D 22,202,037 times, every time on a 1: the halting transition D0 is never close to firing in a way the run shows.

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

The same table as 1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA up to renaming, started in another state; no common configuration in the first 107 steps of each.

Check it yourself

Commands

. /etc/profile.d/lean.sh      # after scripts/setup-lean.sh
holdouts/1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC/lean/check.sh
python3 holdouts/1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC/py/cert.py   # rewrites lean/Tables.lean
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC 1000000000