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

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

Does this machine ever halt?

1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---

Decided by an outside Rocq proof: it haltsA Rocq proof in busycoq pull request 102 (open, not yet reviewed by the maintainer) was compiled here, on busycoq's own definitions, with no axioms beyond Coq's own. It is their proof, not one written in this repository; the ledger below says what this repository checked on its own.

It halts. For a long time it writes runs of equal blocks of 1s and halves them round after round, stopping one cell short of a halt thousands of times. Underneath, it is a table one transition away from a machine DeepMind proved halting, and DeepMind's engine, changed for that transition, shows in Coq that it halts.

KernelhaltsA Coq theorem on busycoq's definitions; the engine needs 688,228 steps, on a tape of about 26326 cells.
Computed109 stepsNo halt in the C simulator; 37,754 cells visited.
native_decide107 stepsNo halt, proved in Lean; the first 10,000 by the kernel alone.
Heuristicn → n/2Each round, every run of equal blocks halves and moves up a level.
Heuristic1.90×1014 stepsNo halt in the accelerated simulator (observed, not proved; checked against direct simulation up to 1.00×1010 steps).
Proved in CoqThe proof: halt : halts tm c0, stated on busycoq's own definitions of a Turing machine and of halting, in holdouts/1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---/coq. Coq 8.18.0 compiles it and Print Assumptions reports no axioms; the build log is next to the files. The proof of 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD--- (DeepMind's busycoq pull request 93 engine changed for T4) with the table, the state map, the start (D) and the final run (run_pow 20) changed; the proved engine's run from blank tape, 688,228 engine steps, is one evaluation of about 12 hours. The generator is tools/coq/t4engine/proof/mkD.py.
An outside Rocq proof, compiled here: it haltsbusycoq pull request 102 (valu42, 2026-11-18) contains a Rocq proof that this machine halts (verify/M_1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RBHHH.v). The pull request is open: not merged and not reviewed by the maintainer. We compiled the file on busycoq's BB6 branch (commit 33209bc) with Coq 8.20.1 on 19 November 2026, in 49618 s: the theorem halt : halts tm c0 is stated on busycoq's own definitions of a machine and of halting, Print Assumptions reports no axioms, and the file's transition table is this machine. It is their proof, not one written in this repository. The verdict on this page rests on this proof.
Community labelIn the community's BB(6) tracker the machine's class is Chaotic Bell 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 1. F is entered only from E1 (writes 0, moves L): 1 E>1. So a halt is the moment this pattern appears, with the head on the cell after >.

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

What the tape is made of

Runs of equal blocks

Watch the run only at the moments the head stands in state A at the left end of the tape. At every such moment the tape is a list of blocks 1k 00 (k ones, then two zeros), and almost every k has the form 6j+1: 1, 7, 13, 19, 25, ... Call j the block's level. Equal blocks come in long runs. Here is the tape at step 448,826,251, each block written as its k, x meaning repetition (so 7x570 is 570 copies of 1700):

58 1/1 13 53 47 49x3 43x4 41 37x18 31x23 25x92 1 17 19x113 7 1 11 13x458 1 5 7x570 5 1x2265 1

The highest levels are on the left, the lowest on the right; the whole tape is 25,736 cells wide. The left part grows only like the logarithm of the time (a new level now and then), the right part like its square root.

One sample to the next

Every run halves

The next sample, at step 560,017,209, reads (the leftmost few blocks left out):

... 43x9 37x11 31x46 7 1 23 25x56 7 1 17 19x228 7 1 11 13x284 11 7x1133 1x1500 1

Compare: the 2265 blocks of level 0 became 1133 blocks of level 1, the 570 of level 1 became 284 of level 2, 458 → 228, 113 → 56, 92 → 46, 23 → 11, 18 → 9. Every run halved and went up a level, and a fresh run of 1500 level-0 blocks appeared on the right. That is the law at every round we checked: n blocks of level j become between ⌊n/2⌋−1 and ⌈n/2⌉+1 blocks of level j+1. So a run born with n blocks survives about log2 n rounds, which is why the number of levels, and the left part of the tape, grows only logarithmically.

How the halving is done: a round is an expanding bouncer. The head runs right into the tape and then zig-zags in a window that widens on both sides a few cells per trip. Going right, it rewrites pairs of ones 11 as 01; going left it rewrites 01 back as 11 (these shift rules are proved in Lean). Doing so it eats one block of a pair and grows the other by six ones.

DeepMind's engine

One transition away from a proved halt, and halting

This machine's table, with its states renamed, is 1RB1RA_1LC0RD_1LD1LB_1RA0LE_0LB0LF_0RA--- started in state D; 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD--- (state B), 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC--- (state C) are the same table started in the other two states. It differs in the single transition F0 from the table of 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0RD---, which DeepMind proved halts (busycoq PR 93) with a fast engine: an evaluator over run-length tapes of macro words whose every step is proved sound in Coq. All of that engine's rules hold for this table except four, the ones that pass through F0. In those, where DeepMind's machine ends in the configuration <C 100, this one ends in <B 1 with 11 more on the right; on the digit words D n = 1 (11)^n 00 of the engine, this moves a carry from the digit on the left to the digit on the right.

We changed the engine at every place that uses one of the four rules (tools/coq/t4engine), extracted it from Coq to OCaml and checked it against direct simulation through 3×1010 machine steps. Run from blank tape in state D, it stops after 688,228 of its steps, on a tape of about 26326 cells, with the head in state F on a 1: a halt. The proof of the same table started in state B (holdouts/1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD---/coq), which redoes DeepMind's soundness proofs for the four changed rules, needs only its table, its state map, its start and a longer final run for this machine. Coq checks the run in one evaluation, so the halt is a theorem (holdouts/1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---/coq).

How it stops

One cell short, until it is not

The machine has one halting transition (F reading a 1), and following the table backwards there is only one way into it: D reads a 0 while the three cells to its left are 1. Lean checks that 1 1 1 D> 0 halts four steps later. In the first 109 steps D read a 0 about 21,000 times, and every single time the cells to its left were 1 1 0: the block to its left had exactly two ones. So whether the machine halts is whether some round ever brings D to a 0 next to a longer run of ones, for instance through one of the odd blocks (5, 11, 17, ...) left over when a run has an odd count.

No short invariant decides it (CTL up to 6 cells, n-gram CPS up to width 7 fail), and the round map has not been worked out. The engine run above settles it without that map: much later, on a tape of about 26326 cells, D does read a 0 next to three 1s, and the machine halts after more than 101904 steps. The exact count is not computed.

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

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 37,754 cells (401 left of the start, 26,856 right), with a density of 1s of 0.618.

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
left559,522,328D>0 1^3 0^2 1^15 0^2 1 0^2 1^51 0^2 1^55 0^2 1^49 0^2 1^49 0^2 1^47 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^3
left705,188,298D>0 1^3 0^2 1^3 0^2 1^59 0^2 1^55 0^2 1 0^2 1^47 0^2 1^49 0^2 1^49 0^2 1^49 0^2 1^49 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^13 0^2 1^29 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31
left875,296,488D>0 1^5 0^2 1 0^2 1^59 0^2 1^53 0^2 1^55 0^2 1^55 0^2 1^49 0^2 1^49 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^43 0^2 1^35 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^37 0^2 1^7 0^2 1 0^2 1^29 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^2 1^31 0^
right959,906,9851^2 0 1 0 1^2 0 1^2 0 1^55 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 1^51 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 1^45 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0
right975,588,3041^2 0 1 0 1^2 0 1^2 0 1^55 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 1^51 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 1^45 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0
right991,309,4231^2 0 1 0 1^2 0 1^2 0 1^55 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 1^51 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0 1^45 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1^2 0 1^2 0

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.

1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB--- (this machine)

What is known

Every result, by what it rests on

Status as of 19 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.

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 37,754 cells have been visited and 23,316 of them hold a 1.

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

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

Kernel
b_run, a_halve, c_halve, c_double, d_double, lean/Rules.lean
The sweeps' shift rules

Moving right, A (with 1 0 behind it) and C (with 1 behind it) turn each pair 11 into 01, 6 steps a pair: a run of 2n ones becomes (01)n. Moving left, C (facing a 0) and D (facing a 1) turn each 01 back into 11, 2 steps a pair. B runs over 1s. Each holds for every n and every surrounding tape.

Kernel
halt_shape, halt_after_shape, lean/Rules.lean
The shape of a halt

From 1 1 1 D> 0 the machine reaches F on a 1 in 3 steps and halts on the next. Conversely (by reading the table, not formalized) F is entered only from E on a 1, E only from A on a 1, and A has a 1 to its left only when it came from D on a 0, so every halt comes this way.

Computed
c/halt_nbhd.c (./halt_nbhd M 1000000000 D 0)
Near misses: D reads a 0 next to exactly two 1s

In the first 109 steps D reads a 0 20,887 times with 1 1 0 to its left (one 1 short of a halt) and 147 times at the blank left end; never with three 1s.

Heuristic
c/samples.c, py/rounds.py
Rounds and the halving law

Sample the run when the head is in A at the left end of the tape (rounds; consecutive samples about 1.25 times further apart). At every sample the tape is a list of blocks 1k 00, almost all with k = 6j+1 and grouped in long runs of equal blocks, lowest level at the right. Between consecutive rounds a run of n blocks of level j becomes a run of ⌊n/2⌋−1 to ⌈n/2⌉+1 blocks of level j+1 (checked for every run of at least 10 blocks after the first 3·106 steps, to 1.7·109), and a new run of level-0 blocks 100 appears, alternately about 0.65 and 1.9 times the previous one. A few odd blocks (k = 5, 11, 17, ...) sit between the runs.

Heuristic
head-position trace of one round (286,681,948 to 356,669,437)
Within a round: an expanding bouncer

After the left-end sample the head runs right to a point well inside the tape and then zig-zags in a window whose left edge creeps left and right edge creeps right (by a few cells per bounce, using the halving and doubling rules above), until the window reaches the left end: the next sample. This is where the square-root growth on the right comes from.

Computed
tools/py/bbtools/ctl.py; tools/c/ngramcps.c (run for the G02 group, not stored here)
No closed tape language from short windows

bbtools.ctl with windows of K = 3, 4, 5, 6 cells finds a closed set, but every one allows a halt (72 to 145 halting abstract configurations); n-gram CPS (widths 3 to 7, with history and LRU) also fails.

Heuristic
holdouts/1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA1RF_0LC---/py/rsim.py, holdouts/1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA1RF_0LC---/py/rsim_screen.py, holdouts/1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA1RF_0LC---/data/rsim_screen.json
No halt in the first 1.90×1014 steps of an accelerated run

Observed, not proved: the accelerated simulator rsim.py ran 1.90×1014 steps from blank tape without reaching a halting transition. Its tape, state and head position were equal to those of a plain C simulator at 6 checkpoints, the last at 1.00×1010 steps. Of these steps, the part after the last checkpoint rests on the simulator alone, including 6,642 trip-level jumps: a jump applies many identical round trips at once after seeing the same tape shape recur with constant count changes, which is validated against direct simulation but not proved.

Computed
holdouts/1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---/lean/T4Rules.lean
The four rules where it departs from DeepMind's halting sibling

The four changed macro rules are proved in Lean for 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC---, the same table started in state C; they are statements about the table, so they hold here after the renaming of states, which is not itself checked in Lean.

Kernel
halt, coq/H67137.v; generator tools/coq/t4engine/proof/mkD.py
It halts: DeepMind's engine, changed for this table, proved in Coq

The engine of busycoq PR 93, with the four rules that pass through F0 changed and every lemma built on them redone (the proof of 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD---, retargeted to this table and start D), reaches a halting configuration from blank tape after 688,228 engine steps, on a tape of about 26326 cells. Coq 8.18.0 checks the run in one evaluation (about 12 hours); Print Assumptions halt: closed under the global context.

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

The same table as 1RB1RD_1LC0RE_1LD1LC_1RA0LB_0RD0RF_0LC--- up to renaming and mirroring, started in another state; no common configuration in the first 107 steps of each. The same table as 1RB0LC_1RC1RA_1LD0RE_1LA1LD_0RA0RF_0LD--- 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/1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---/lean/check.sh
gcc -O2 -o triage tools/c/triage.c && ./triage 1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB--- 1000000000
gcc -O2 -o samples holdouts/1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---/c/samples.c && ./samples 1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB--- 2000000000 A L 0 100000 > left.txt && python3 holdouts/1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---/py/rounds.py left.txt
sh holdouts/1RB0LE_1RC1RB_1LD0RA_1LA1LC_0LC0LF_0RB---/coq/build.sh /path/to/busycoq      # the Coq proof; a checkout of busycoq's BB6 branch; about 12 hours