Busy Beaver Explorer / holdouts / 1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_---1LE / explained
A 6-state Busy Beaver machine · Status as of 16 November 2026.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.
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.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 >.
| state | reads 0 | reads 1 |
|---|---|---|
| A | 1 R B | 1 R D |
| B | 1 R C | 1 R B |
| C | 1 L D | 0 R A |
| D | 1 R A | 0 L E |
| E | 1 L F | 0 L C |
| F | halt | 1 L E |
read:write move. Red marks a halting transition. Hover a state or a row to single out its arrows.This is the real machine, simulated in your browser. Step it, play it, or jump to a step count. Below the cells is the whole visited tape in the notation of the notes: 1^5 is five 1s, and C>0 is the head in state C on a 0.
(10)7 is the word 10 seven times in a row, and the orange tag is the head. The grouping is found afresh at every step by looking for the longest repeat of a word of up to 8 cells, so it shows the counts a machine keeps on its tape without anyone having to decode them first; it is a display, not a result.The diagram stacks the tape at many moments. Sampling at each new cell shows the shape of the run as the visited region grows; sampling evenly in time shows where the head spends its time. The records list every step at which the head reaches a cell no earlier step reached, with the side, the width so far and the whole tape: the first place to look for a repeating macro structure. Click a row of the diagram to send the simulator above to that step.
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).
mstep_sound
Level 3Visits of a zone
011 with bits between them. One unit is one visit: 6(n0 + … + ni−1) + 4i + 11 steps.visit
Level 4The odometer of tanks
jump
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.
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.
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:
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.
(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.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.
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 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.
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).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.
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 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.
| statement | where | what it rests on |
|---|---|---|
halts : HaltsFromBlank (Lean) | lean/Halt.lean | native_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.v | Kernel 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 K | the same file | Kernel 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 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.
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.
The two machines run for the same number of steps and are drawn the same way, a row each time the head reaches a new cell. Where the relation involves a mirror image, the second diagram is flipped left to right so that the two can be compared directly. Look for where the pictures agree and where they part: the text under each relation in the section on related machines says which of it is proved and which is only observed.
Status as of 16 November 2026. The same list as the proof-status page, built from the same file.
step_none_iff, lean/Blank.leanThe machine stops exactly when it reads the symbol of a halting transition (F0); the generated statement covers every configuration.
blank_runs_kernel, lean/Blank.leanThe list simulator of the shared library, proved to agree with the machine's semantics, runs 10,000 steps from blank tape without a halt, evaluated by Lean's kernel.
blank_runs_native, lean/Blank.leanThe same run, evaluated by compiled code.
halts_172044, run_halts, coq/M_1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_HHH1LE.vhalts_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).
steps_172044, jump, Jz_succ, round_sound, coq/M_1RB1RD_1RC1RB_1LD0RA_1RA0LE_1LF0LC_HHH1LE.vsteps_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.
run_halts, halts, lean/Halt.leanThe 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.
visit, lean/Zone.leanWhen 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.
jump, addV_succ, inc_physP, lean/Jump.leanIn 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.
mstep_sound, tryJump_sound, run_sound, lean/Sim.lean, lean/Run.leanEach 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).
py/accel.py, py/odo.py, py/leansim.py853177647932005270554892218084645935472995035642746848454477793277027802995098762076895667304703808111420498351739937140047615589683 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.
py/check.py, c/visits.c, c/tok.cpy/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.
py/accel.pyAt 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).
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.
holdouts/related.json, written by holdouts/related.py compute (tools/c/cfgmatch.c, tools/c/lockstep.c)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.
. /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)