Busy Beaver Explorer / holdouts / 1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE / explained

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

This machine halts, after 8.5·10131 steps

1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE

Decided: it haltsProved in this repository, checked by Lean and by Coq. The ledger below says what each part rests on.

Lean and Coq both prove that it halts, and Coq proves after exactly how many steps: a simulator that is proved to follow the machine runs it from blank tape to its halting transition. The machine keeps a binary odometer on its tape whose digits are fuel tanks; the tanks drain exponentially slowly, the odometer grows to 215 digits, and one day the carry runs off the left end of the tape. The simulator below runs the real machine, but it would need far longer than the age of the universe to get there.

KernelIt haltsProved in Coq, checked by the kernel; also in Lean.
Kernel8.53·10131Steps before it halts; the exact number is proved in Coq.
Computed2.9·1066Cells of tape at the end, in 215 counters.
Kernelevery zoneThe odometer rule and its closed form for V visits, proved for all sizes.
Also proved in CoqA second proof assistant checks the same result: M172044.halts_172044 : halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/coq. Coq 8.18.0 compiles it and Print Assumptions reports no axioms; the build log is next to the files. It also proves the exact number of steps (steps_172044: the halting configuration is reached after exactly 853177647932005270554892218084645935472995035642746848454477793277027802995098762076895667304703808111420498351739937140047615589682 steps, and only then). It is the method of the Lean proof with two block rules that cross a whole counter level in one round and a step count in every lemma; the run from blank tape is 19.0 million rounds, evaluated by vm_compute in about 8.5 minutes, so this proof does not trust a compiler. The theorem printed above is the halting one; steps_172044 in the same file states the count. A shorter proof of the same theorem (the same proof without step counts, 1,272 lines, checked by Coq 8.18 in about 2 minutes 45 seconds, and submitted upstream as busycoq pull request 76) is on a branch of our fork of busycoq, ready to be proposed upstream: project-thread-kihhxw.
Community labelIn the community's BB(6) tracker the machine's class is Skelet 1-like Class 1. 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 0. F is entered only from E0 (writes 1, moves L): 0 E>0. So a halt is the moment this pattern appears, with the head on the cell after >.

statereads 0reads 1
A1 R B1 R D
B1 R C1 R B
C1 L D0 R A
D1 R A0 L E
E1 L F0 L C
Fhalt1 L E
One circle per state. A solid arrow is taken on reading 0, a dashed one on reading 1; its label is read:write move. Red marks a halting transition. Hover a state or a row to single out its arrows.
Follows the simulator below. The orange state is the current one and the thick arrow is the transition about to fire. The bars count how often each transition has fired since step 0, so the rare ones stand out.
Watch it run

The tape from blank, step by step

This is the real machine, simulated in your browser. Step it, play it, or jump to a step count. Below the cells is the whole visited tape in the notation of the notes: 1^5 is five 1s, and C>0 is the head in state C on a 0.

Jump to:
step 0state Acells visited 1ones 0
Cells around the head (dark = 1, dashed = never visited).
The same tape, grouped into repeated words: (10)7 is the word 10 seven times in a row, and the orange tag is the head. The grouping is found afresh at every step by looking for the longest repeat of a word of up to 8 cells, so it shows the counts a machine keeps on its tape without anyone having to decode them first; it is a display, not a result.
The run at a glance

Space-time diagram and records

The diagram stacks the tape at many moments. Sampling at each new cell shows the shape of the run as the visited region grows; sampling evenly in time shows where the head spends its time. The records list every step at which the head reaches a cell no earlier step reached, with the side, the width so far and the whole tape: the first place to look for a repeating macro structure. Click a row of the diagram to send the simulator above to that step.

Four levels

From six states to an odometer of fuel tanks

The question "does this machine halt, and when?" can be asked at four levels of description. Each level keeps less detail than the one above it and has a coarser unit of time, and each step down is a theorem saying that the lower level follows the machine exactly. At the bottom a program built from levels 2 to 4 runs from blank tape to the halting transition; that run is the proof (the bottom line).

The visits that are not of the regular form (a tank nearly empty, or the binary number overflowing) have no rule at level 3 or 4; the program runs them at level 2. Lean proves that whatever mixture of rounds and jumps the program makes is a run of the machine (run_sound, kernel), and evaluates the program from blank tape with compiled code (run_halts, native_decide). Coq does the same with the exact step count, checked by its kernel.

One moment, four descriptions

Pick a visit. The browser runs the real machine cell by cell from blank tape to that moment, and separately runs the compressed-tape program to the same moment. The rows show the same instant at each level; the marks say whether the computations agree.

visit 59
1 · Machine
counters (011)n, alternatelythe bits 11 and 01 between themother wordshead, state Adark = 1, pale = 0
2 · Compressed
3 · Visit
4 · Tanks
Visit 2,500 is 8.66 million steps in; the browser redoes the run from blank tape when you go back. Counts of fewer than three copies of 011 are written out as cells, so a nearly empty tank shows up as an irregular word.
Level 1 to level 2

The compressed tape

The first step down replaces the tape by a compressed tape: two stacks of items, one on each side of the head, where an item is a single cell or a word repeated n times, for any n. A round of the program (mstep in lean/Sim.lean) is one of four things:

  • a transition: the head reads the cell in front of it and the machine makes one step;
  • a run crossed: in front of the head lies a run of copies of a word, and one copy, entered in some state, is left on the far side in the same state. Then every copy is crossed in the same way, so the whole run is crossed at once and the steps are multiplied out;
  • two copies crossed: the same with two copies of the word taken together;
  • a copy unpacked: otherwise one copy is taken off the run and written out as cells.

Leftward moves are handled by mirroring the table, so one rule covers both directions (steps_mir). Kernel mstep_sound: every round leads from the configuration the stacks stand for to the next one by real steps of the machine, whatever is on the stacks. How the program folds cells into runs only affects its speed, never its correctness.

The stepper runs the program and the plain machine side by side. After every round the machine is moved on by the number of steps the round claims, and the two tapes are compared cell by cell.

round 0step 0items 0
Runs are shown in tape order, (011)8 for eight copies of 011; the orange tag is the head and the side it faces. The log lists the last rounds, newest first.
Level 2 to level 3

One visit is a binary increment

Look at the tape each time the head, in state A, steps onto a fresh cell at the right end (a visit). Write n for the word 011 repeated n times. Then the tape is a list of counters with two-cell words between them, for example at visit 59 (step 10,094):

11 01 8 01 5 01 45 0 A>        that is  (011)^11 01 (011)^8 01 (011)^5 01 (011)^45 0

The words between counters are 11 or 01. Read 11 as the bit 0 and 01 as the bit 1: the tape carries a binary number, one bit between each pair of counters.

n3 = 12n2 = 9n1 = 7n0 = 34 1111110 A> bit 0bit 0bit 0 −1 per 8−1 per 4−1 per 2+2 per visit each visit adds 1 to the binary number written by the bits; tank j pays one unit every 2^j visits

One visit adds 1 to that binary number, exactly as a car's odometer ticks: the bits at the right end that are 1 turn to 0, and the first 0 bit turns to 1. The head walks left only as far as that bit and comes back, so most visits are short.

The counters pay for it. The counter left of a bit loses one unit each time the bit is set (after the bookkeeping of the units that cleared bits pass along), and the last counter gains 2 at every visit. So the counter next to bit j is a tank that loses one unit every 2j visits: the last tanks drain fast, the first ones almost never. A visit that sets bit i takes 6(n0 + … + ni−1) + 4i + 11 steps.

Because the rule is this regular, any number of visits can be applied at once with a formula, as long as no tank runs low and the number does not overflow. That is what lets a program follow the machine for 10131 steps.

Kernel visit in lean/Zone.lean states this for every number of counters, every count and every tape left of the zone: if inc, the increment with its bookkeeping, applies to the bits and counts, the machine goes from the zone to the incremented zone. The proof follows the head: it walks left through the counters behind the 1 bits (state D turns each 011 into 100), turns at the 0 bit, and walks back (state C turns 100 into 011). inc gives no answer when every bit is 1 (an overflow) or a count that must pay is 0; those visits are the irregular ones.

Type a zone (counts and the two-cell words between them, ending with n0 and the 0), choose what lies left of it, and make a visit. The browser builds the tape, runs the real machine until the head is back in A at the right end, and compares the result with the rule. The picture is the visit in space and time: one row per moment, the head's path in orange.

The picture shows the tape of the zone, cell by cell, at the start of the visit (top) and the head's position as time goes down. Each click continues from the result; the log keeps the visits made, newest first.
Level 3 to level 4

Many visits at once: the tanks

The bookkeeping of a visit (a count loses one, a cleared bit moves one unit up) looks fiddly in the counts nj of the tape. In the coordinates

N_0 = n_0 − s_1,    N_j = n_j + s_j − s_(j+1),    N_k = n_k + s_k          (s_j the bits)

it becomes plain: at every visit N0 gains 2, and Nj−1 loses 1 each time bit j is set. Bit j is set once every 2j visits, so Nj−1 is a fuel tank that drains at that rate, and after V visits everything is known in closed form: bit j has seen about V/2j−1 increments, half of which set it (addV in lean/Jump.lean).

Kernel jump: if the bits do not overflow within V visits and every Nj (j ≥ 1) is still at least 2 after them, the machine goes from the zone to the zone after V visits. The proof is an induction on V: addV_succ says that one more increment after addV V is addV (V + 1), and inc_physP that the increment in these coordinates is the visit rule of the tape. The Coq proof adds the number of steps of V visits in closed form, a sum over the levels of the odometer.

The panel starts from the zone of visit 94,957 of the run, where the program jumps 16,383 visits in one go. Move V. The bars are the tanks; the lamps are the bits. The browser computes the zone after V visits with the closed form, again by V single visits of the rule, and, when it is short enough, by running the machine itself.

V = 0 of at most 0
The largest V is the one the theorem allows: no overflow, and every tank N1, …, Nk at least 2 at the end. The Lean program keeps a margin of 6 (chooseV), so it stops a little earlier and handles the visits near an empty tank on the compressed tape. Bars are scaled per tank to its value at V = 0 (the last tank, N0, only grows).
The irregular part

Tanks that run dry, and overflows

When a tank is down to a few units, or when all bits are 1 and the carry runs past the last of them, the tidy picture breaks for a few visits: the words between counters become other short words (11101, 11101111, 1101101101, …), neighbouring counters merge or a new one splits off, and then an odometer is back with other contents. Nobody has a formula for these visits; the program runs them step by step on a compressed tape, where a run of a million copies of 011 is one item. There are 116,906 such visits in the whole run, between 86,729 formula jumps.

The first counter of the list is the slowest tank. It ran dry four times, near visits 105, 1014, 1039 and 1066. Three times the scrap it left at the left end turned back into a regular left end.

How it ends

The carry falls off the tape

The fourth time, the scrap was a different word, 11101101111101111, and each later overflow of the whole odometer ate a piece of it: 11101101111101, 11101101101, 1101101, 11111101111, 11111101, 11101111, 11101, 1111, 1. With a single 1 left, the tape was

1 91562 01 6921 01 256717 01 ... 01 (2.5·10^65) 0 A>       215 counters, every bit 1

and the next carry walked through all 215 counters, 2.9·1066 cells, found nothing to stop it, and the machine read a 0 in state F on blank tape left of everything: the one halting transition. The total is

853177647932005270554892218084645935472995035642746848454477793277027802995098762076895667304703808111420498351739937140047615589683 steps.

The bottom line

It halts, at a step with 132 digits

The machine 1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE halts from a blank tape, at step

853177647932005270554892218084645935472995035642746848454477793277027802995098762076895667304703808111420498351739937140047615589683

(bbchallenge count, the halting transition F0 included; about 8.53·10131), after 9.6·1065 visits of the right end, at the left end of a tape of about 2.9·1066 cells.

statementwherewhat it rests on
halts : HaltsFromBlank (Lean)lean/Halt.leannative_decide the kernel for visit, jump, mstep_sound and run_sound; one compiled evaluation, run_halts : run 100000000 start = true, so Lean's compiler is trusted besides the kernel and the three standard axioms
halts_172044 : halts tm c0 (Coq, busycoq's definitions)coq/M_1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_HHH1LE.vKernel no axioms (Print Assumptions: closed under the global context); the run is evaluated by vm_compute and checked by Coq's kernel
steps_172044 : halts_in tm c0 (N.to_nat K) /\ forall n, halts_in tm c0 n -> n = N.to_nat Kthe same fileKernel K is the number above minus one: the machine reaches its halting configuration after exactly K steps and at no other time

The Lean proof shows that it halts, not after how many steps; the exact count is the Coq theorem, and three separately written Python simulators give the same number. Not known: a closed rule for the irregular visits, and so any reason for the halt shorter than the run itself.

The whole run, in your browser

The program of the proof, written again in JavaScript with exact big integers: the compressed tape of level 2, and at every visit the jump of level 4 when its conditions hold (the same choices as lean/Run.lean: counts of at least 7, a margin of 6, at least 8 visits). It counts steps as it goes, a jump with the closed form of the Coq proof. The second choice adds the two block rules of the Coq proof, which cross a whole counter level in one round. Either way it takes several seconds; the picture shows the odometer growing, one dot per jump.

rounds 0jumps 0visits 0steps 0counters 0time 0 s
Across: the number of visits, on a log scale up to 1066. Up: the number of counters in the zone the jump read; a zone is read only as far as its counts are at least 7, so many jumps see part of the odometer, and the upper edge is the whole of it. Every transition, run crossed, copy unpacked, block rule and jump counts as one round.
How sure is this

Proved in Coq and in Lean, step count included

The halt is a theorem checked by Lean. The proof has two parts. First, a small simulator written inside Lean is proved to follow the machine, whatever the tape: it keeps the tape compressed (a run of a million copies of 011 is one item), crosses a whole run when one copy is crossed in the same state, and at each visit may apply the odometer rule for many visits at once. That rule, and its formula for V visits, are proved for every odometer size. Second, Lean runs this simulator from blank tape: after about 89 million rounds it meets the halting transition. This last step is a compiled evaluation (native_decide), so it trusts Lean's compiler; everything else is checked by the kernel.

The same proof is also written in Coq, on the definitions of busycoq, the library in which the bbchallenge results are proved. There the run is evaluated by Coq's kernel virtual machine (vm_compute), so the Coq theorem does not trust a compiler. It is also faster, thanks to two more rules. When the odometer overflows, the head walks across every counter and back, and that walk is almost all of the work: 99% of the Lean simulator's rounds. A counter level looks like 1 0 (011)k 1 on the way left and (100)m 1 0 1 1 0 on the way back; the two rules cross such a level in one round, whatever k and m are, and are proved for every k and m. With them the run is 19 million rounds instead of 89 million, and takes under 3 minutes without counting steps.

The Lean proof shows that the machine halts, not after how many steps. The Coq proof also counts: every rule in it says exactly how many steps it takes, a visit of the odometer and a jump over many visits included, and the simulator adds them up as it runs. So the 132-digit number below is a theorem too, and being exact it is also the best possible lower and upper bound. It is the number the Python programs in the repository had computed: three simulators written separately, tested against a plain cell-by-cell simulator, give it as well. Counting makes the Coq run slower, about 8.5 minutes instead of under 3, because the formula for a jump multiplies numbers of a few hundred digits.

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.

1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE (this machine)

What is known

Every result, by what it rests on

Status as of 16 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 (F0); 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
halts_172044, run_halts, coq/M_1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_HHH1LE.v
The machine halts: a second proof, in Coq (busycoq)

halts_172044 : halts tm c0 on the definitions of busycoq's BB6 branch, with no axioms. The same method as the Lean proof (the visit rule and the closed-form jump, proved for every zone; a run-length simulator proved to follow the machine) plus two block rules that cross a whole counter level in one round (D leftwards over 1 0 (011)k 1, C rightwards over (100)m 1 0 1 1 0, proved for every k, m). They bring the run from 88.9 to 19.0 million rounds. The run from blank tape to F0 is evaluated by vm_compute, which the kernel checks: about 8.5 minutes with the step counts below (160 seconds without them, in an earlier version on the busycoq fork).

Kernel
steps_172044, jump, Jz_succ, round_sound, coq/M_1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_HHH1LE.v
The exact number of steps: 8.53·10131

steps_172044 : halts_in tm c0 (N.to_nat K) /\ forall n, halts_in tm c0 n -> n = N.to_nat K, with K = 853177647932005270554892218084645935472995035642746848454477793277027802995098762076895667304703808111420498351739937140047615589683 minus one: the machine reaches its halting configuration after exactly K steps and at no other time, so it runs for K + 1 steps with the halting transition (the bbchallenge count). Being exact, this is also the best possible lower and upper bound. Every lemma of the Coq proof states its number of steps (busycoq's multistep). A visit takes 6(n0+…+ni−1) + 4i + 11 steps. V visits take a closed form, 11V + 6V(V−1) plus a sum over the levels of the odometer (Jz), proved by induction on V. The run carries its count and ends with run 225 start = RHalt K.

native_decide
run_halts, halts, lean/Halt.lean
The machine halts from blank tape

The simulator of lean/Sim.lean and lean/Run.lean, started on blank tape, meets the halting transition F0 within 108 rounds (about 88.9 million: 68.6 million single transitions, 13.4 million runs crossed, 86,734 jumps). With run_sound this is halts : HaltsFromBlank. The evaluation is compiled, so it trusts Lean's compiler; about 6 minutes of CPU.

Kernel
visit, lean/Zone.lean
The visit rule of a zone, for every zone

When the tape ends in counters (011)nk … (011)n0 separated by 11 (bit 0) or 01 (bit 1), one visit is a binary increment of the bits: the lowest 0 bit si is set, ni loses 1, every bit cleared moves one unit to the counter on its left, n0 gains 2. Proved for every number of counters, every count and every tape left of the zone, by induction on the carry.

Kernel
jump, addV_succ, inc_physP, lean/Jump.lean
V visits at once

In the coordinates N0 = n0 − s1, Nj = nj + sj − sj+1 a visit is a plain binary increment in which Nj−1 loses 1 when bit j is set and N0 gains 2. For every V after which the bits have not overflowed and every Nj is still at least 2, the machine goes from the zone to the zone V visits later, given in closed form.

Kernel
mstep_sound, tryJump_sound, run_sound, lean/Sim.lean, lean/Run.lean
The simulator follows the machine

Each round of the run-length simulator (one transition, a run of a word crossed when one or two copies are crossed in the same state, a copy unpacked, or a jump whose hypotheses it has checked) takes the configuration it stands for to a configuration the machine reaches; if it answers true, the machine halts. The leftward half of the simulator is the mirror image of the rightward half (steps_mir).

Computed
py/accel.py, py/odo.py, py/leansim.py
The number of steps, by three Python simulators

853177647932005270554892218084645935472995035642746848454477793277027802995098762076895667304703808111420498351739937140047615589683 steps (the halting transition counted), 9.6·1065 visits of the right end. The same number as the Coq proof; the Lean proof does not count steps. py/accel.py (86,729 closed-form jumps, 116,906 visits on a run-length tape), py/odo.py (the jumps composed by doubling instead of the closed form) and py/leansim.py (the Lean simulator's algorithm, 86,734 other jumps) give the same number.

Computed
py/check.py, c/visits.c, c/tok.c
The Python simulators against a cell-by-cell run

py/rl.py agrees with the cell-level reference simulator on step count and whole tape at each of the first 3,000 visits, with the plain C simulator on step count and number of 1s at each of the first 20,000 visits; the visit rule with its step count 6(n0+…+ni−1) + 4i + 11 agrees with the cell-level simulator on 6,000 random zones; the accelerated run agrees with rl.py alone up to visit 429,738 and with the C run-length simulator c/tok.c at 57 checkpoints up to step 1015.

Computed
py/accel.py
How it ends

At the last visit the tape is 1 n214 01 n213 01 … 01 n0 0 with n214 = 91,562 and n0 about 2.5·1065: every bit is 1, the carry crosses all 215 counters in one walk of 2.9·1066 steps and F reads a 0 at the left end. The word at the left end had been eaten over the previous overflows (11111101111, 11111101, 11101111, 11101, 1111, 1).

Heuristic
README
The irregular visits

When a counter runs low or the bits overflow, the words between counters change (11101, 11101111, 1101101101, …) and counters merge or split; no closed rule is known for these visits, they are simulated (in the Lean proof too). The first counter ran out four times (near 105, 1014, 1039 and 1066 visits); three times the left end recovered, the fourth time it did not.

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

The same table as 1RB0LC_1LC0RE_1LD1LB_1LA1LD_1RF0RA_---1RE up to renaming and mirroring, 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/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/lean/check.sh          # about 10 minutes; prints the axioms of visit, jump, run_sound, halts
sh holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/coq/build.sh /path/to/busycoq     # Coq 8.18, busycoq's BB6 branch; about 9 minutes; prints the axioms of halts_172044 and steps_172044
python3 holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/py/accel.py          # the run to the halt with its step count, about 2.5 minutes
python3 holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/py/coqsim.py        # the Coq simulator's algorithm in Python, about 1 minute
python3 holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/py/leansim.py        # the Lean simulator's algorithm in Python, about 3 minutes
python3 holdouts/1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE/py/check.py quick    # the checks of the Python simulators, 15 s (full: 5 min)