Busy Beaver Explorer / 1RB0LF_1RC0LB / explained

A 6-state Busy Beaver machine ยท Status as of 6 November 2026.

Does this machine ever halt?

1RB0LF_1RC0LB_1RD1RB_1RE1RF_1LA---_0RC1LA

Nobody knows. Started on a blank tape, this Turing machine has run for ten billion steps without stopping, and in that time it has visited only 642 cells. This page runs the real machine in your browser and lists what is known, each result marked by what it rests on. It grows as the work does.

native_decide108 stepsNo halt, proved in Lean through the macro machine; the first 20,000 steps by the kernel alone.
Computed1010 stepsNo halt in the C simulator; 313 ones and 642 cells visited at the end.
Computed5·1012 macro stepsThe macro machine, as two stacks, never gets stuck; two near misses, both before 2.1·109.
KernelHalts only at D>0 1The one way to stop: D reads a 0 with a 1 to its right.
KernelHalts only at a gap of 3A pass crosses gaps of 1 and 2; it halts exactly when the next gap has length 3.
ComputedNo odd runsAt every pass start in 1010 steps, runs of length 3 or more are even, so no gap of 3.
KernelA macro machinePass to pass, the run is a map on a stack and a list of lengths; it halts only if that map gets stuck.
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 E reading 1. E is entered only from D0 (writes 1, moves R): D>0 1. 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 R C0 L B
C1 R D1 R B
D1 R E1 R F
E1 L Ahalt
F0 R C1 L A
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.

Macro structure

Passes, and the one way to halt

Watch the simulator for a while and the head settles into a rhythm. Moving right, states C and B fill a sparse stretch of tape, single 1s with short runs of 0s between them, into solid 1s: C>1 0 1 0 becomes 1 1 1 1 C>. Moving left, A and F turn a solid block back into alternating cells, 1 1 1 1 A>1 into A>1 1 0 1 0, and B erases blocks. Left of the head the tape is solid, right of it sparse.

Call a run of 0s between two 1s a gap. A rightward run, a pass, starts when F or B reads the first cell of a gap and moves right. C crosses every gap of length 1 or 2, and the first gap of another length ends the pass:

This is proved in Lean, checked by the kernel, for any number of crossed gaps (pass_outcome in lean/Pass.lean). So the machine halts exactly when some pass meets a gap of 3 before any other gap longer than 2.

It never has. In ten billion steps every run of 0s or of 1s of length 3 or more, between cells of the other symbol, has had even length at every pass start. A pass that ends at a gap of 4 or more uses up 4 of its cells, which keeps the parity; B erases an even block and a few cells beside it, and the pass that follows refills four of them, which again leaves an even run. If that parity can be proved to last forever, the machine never halts. That proof is the open step.

Most passes end at a gap of 6, half as many at 10, a quarter at 14, and so on: gaps of 4j + 2, each about half as common as the last. That is how the digits of a binary counter behave, and the tape grows about as slowly as a counter does: 199 cells after a million steps, 642 after ten billion.

Macro structure

From pass to pass: a machine on lists of numbers

Stop the simulator whenever a pass is about to start and the tape always looks the same way. Left of the head is a stack of solid blocks of even length, 1^(2s+2), separated by single 0s. The head stands on a gap of 2h + 2 cells. Right of it is a word: segments (0 1)^m separated by gaps of 2n + 2 cells, where n = −1 means two 1s side by side.

The states alternate. A pass from B fills four cells of its gap and sweeps back over the top block of the stack, which becomes a segment in front of a gap four cells shorter. A pass from F runs right over every gap with n = 0, pushing each segment it crosses onto the stack as a block, and stops at the first other gap. If that gap has n ≥ 1 it shrinks by 2, and the last block pushed is erased again and becomes B's next gap. If it has n = −1, the segment after it loses one 0 1.

Lean proves these three rules for every value of the parameters (mstep_sound in lean/Macro.lean), and the C simulator checks them against all 344,806,676 pass starts of the first ten billion steps. The rules fail only when two 1s side by side touch an empty segment; then a gap of odd length appears, and only a gap of odd length can turn into the fatal gap of 3. So the machine halts only if this macro machine gets stuck (no_halt_of_macro).

If every number is even, nothing can go wrong: each rule turns even numbers into even numbers, and a gap counting down by 2 from an even value reaches 0 and is crossed, never −1. Lean proves this for all values (even_run in lean/Parity.lean), and also that odd numbers are born only at the left end of the tape, one each time the stack runs empty, and otherwise disappear in pairs or at the right end (oddc_le). In the run there have never been more than four of them at once, and only 546 of 344,806,676 passes have met two 1s side by side. Proving that the odd numbers never line up badly is the open step.

The ruler-like tally of pass endings is visible here too: B's head gap is h = m + 2 for the last segment m the previous pass crossed, and h = 2, 4, 6, 8 occur with frequencies that halve exactly. The first nonzero gap is counted down by 2 per round, like the lowest digit of a counter.

Open question

Safe by design, or lucky so far?

Write the macro machine as two stacks and its right stack becomes a call stack: each entry is a frame, a loop with a few turns left that pushes its value when it is done. Odd numbers are the only danger. When a frame's own countdown is odd it ends one step early, and that step takes 1 from the frame that called it, a flip. A frame created with value 2 can take two flips; the third gets the machine stuck, and that is the only way the machine can ever halt.

In a hundred billion steps of this two-stack form the run has made 1,181 flips and has twice left a frame at 0, both times on a frame with no turns left, so nothing happened. To test whether something deeper protects it, take snapshots of the run, change one to three even numbers by 2 (every parity stays the same), and let each copy run. About one copy in seventy-five gets stuck within 108 to 109 steps, always in the same way: a value-2 frame near the bottom of the call stack is flipped twice and then hit once more.

Measured per flip, the run is indistinguishable from these copies. The same share of flips land on value-2 frames, second flips are as common, and the copies' stuck rate predicts a 17 % chance that the run would already have got stuck. The copies also stay risky for as long as they run, and the run keeps making about 200 flips per decade of steps. So there is no sign yet of the exact-value invariant a proof of non-halting would need. If the run behaves like its copies, it gets stuck with chance 2 to 3 % per decade: a halt that is likely but astronomically far away, perhaps around 1035 steps. That is a statistical model, not a proof, and a steady decline in the risk over time, which the copies hint at but do not show clearly, would change it.

What is known

Every result, by what it rests on

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

Kernel
step_none_iff, halt_shape, lean/Blank.lean
The halting configurations

The machine stops exactly in state E reading a 1, and D>0 1 halts after one more ordinary step, whatever the rest of the tape.

Kernel
blank_runs_20000, blank_at_63, lean/Blank.lean
No halt in the first 20,000 steps

The list simulator of the shared library, proved to agree with the machine's semantics, runs 20,000 steps from blank tape without a halt, evaluated by Lean's kernel. At step 63 the tape is 0 1^2 0 1^4 C>0 (blank_at_63).

Kernel
pass, pass_outcome, start_F, start_B, lean/Pass.lean
Which passes halt

A pass starts when F or B reads a 0 and moves right; C then crosses every gap of length 1 or 2 (by induction over any list of them). The first gap of another length ends the pass: a gap of 3 halts, a gap of 4 or more turns left at E, two 1s side by side turn left at B or F. So a pass halts exactly when the first gap it meets that is not 1 or 2 has length 3.

Kernel
sweep, sweep_end_odd, sweep_end_even, erase, erase_end, lean/Pass.lean
The leftward pieces

A and F turn 1^(2k) A>1 into A>1 (1 0)^k; B erases 1^k; at the 0 left of a block an odd block starts a pass and an even block starts B erasing the block before it.

Kernel
mstep_sound, blank_to_M0, no_halt_of_macro, lean/Macro.lean
The macro machine

At every pass start the tape is a stack of solid blocks 1^(2s+2) separated by single 0s, the head on a gap of 2h+2 cells, and a word of segments (0 1)^m and gaps 0^(2g) 1. A function mstep on these numbers gives the next pass start, and Lean proves the machine goes there, for all values of the parameters. mstep fails only at a gap g = 0 (two 1s side by side) next to an empty segment. So if the macro machine never gets stuck from the configuration after 12 steps, the machine never halts.

Kernel
phi_interior, phi_end, phi_bottom, lean/Counter.lean
A conserved counter

Read as a recursive program (the right stack of the two-stack form is a call stack), the macro machine keeps a sum Φ: the stack, plus the head gap, plus m + g − 1 for every segment m and gap g of the word. A pass that ends inside the word and a B step with a nonempty stack leave Φ unchanged; a pass that runs into the last segment adds 2 or 1; B with an empty stack takes 1 off. So Φ counts the passes that reach the right end, up to the rare steps at the left end. It does not by itself rule out getting stuck.

Kernel
even_not_stuck, even_step, even_run, oddc_le, oddc_run, lean/Parity.lean
Odd numbers are the only danger, and come from the left end

If every stack entry, segment and gap n = g − 1 is even (the last segment may be anything), the macro machine is not stuck and stays all-even until B has an empty stack, for all values. The number of odd numbers goes up only when B has an empty stack, by exactly 1; otherwise a step keeps it, takes 2 off (two odd numbers cancel), or loses 1 at the last segment. So after t steps there are at most 1 + (visits to the left end) odd numbers; in the first 3·106 macro steps there are 38 such visits and never more than 3 odd numbers at once.

native_decide
blank_runs_10M, lean/Blank.lean
No halt in the first 10,000,000 steps

The same run for 107 steps, evaluated by compiled code.

native_decide
macro_runs_100M, blank_runs_macro_100M, mok_iff, lean/MacroRun.lean
No halt in the first 108 steps, through the macro machine

Compiled evaluation runs the macro machine 108 steps from the pass start after 12 steps without getting stuck; the loop it runs is proved equal to mrun by the kernel, and mrun_sound turns it into at least 108 machine steps without a halt (in fact billions).

Computed
tools/c/tmrun.c, tests/test_machine.py
No halt in the first 1010 steps

The shared C simulator runs 1010 steps from blank tape without a halt; the tape then holds 313 ones and the head has visited 642 cells. The C simulator agrees with the Python reference simulator on the first 80 records of the run (a test).

Computed
tools/py/bbtools/invariants.py
No simple conserved quantity

No a·ones + b·pos + W[state] is conserved modulo 2 to 12, so a linear invariant like the first holdout's mod-3 count does not exist here.

Computed
c/passes.c, py/passes.py check, tests/test_passes.py
No pass meets a gap of 3, and runs stay even

In the first 1010 steps there are 344,806,676 pass starts. At each one c/passes.c reads the cells ahead and finds the gap that will end the pass: never a gap of 3. And every run of 0s or 1s of length 3 or more between cells of the other symbol (away from the head) has even length: no odd run at any pass start. A Python version also runs each pass and checks the prediction against the machine (no mismatch in 106 steps).

Computed
c/macro.c, py/macro.py check, tests/test_macro.py
The run follows the macro machine

Run side by side with the machine, the macro machine predicts every one of the 344,806,676 pass starts in the first 1010 steps, cell for cell over the whole tape, and never gets stuck. Python agrees with C, and with the machine on all small configurations.

Computed
c/fastrun.c, c/twostack.c, py/accel.py, tests/test_accel.py, tests/test_macro.py
The two-stack form does not get stuck in 5·1012 steps

The macro machine written as two stacks (each step one F pass and one B pass) does not get stuck in its first 5.1·1012 steps (of the order of 1014 to 1015 machine steps), run by a plain C simulator at about 4 s per 109 steps; a second C program that follows every frame by identity agrees up to 2·1011. Two flips leave a frame at value 0 (steps 204,719,421 and 2,084,922,784), both on frames with no turns left, and none happen after that; there are 1,923 R2 steps by 5.1·1012. The fast simulator equals the Python rules step by step for 20,000 steps and an exact memoized Python simulator after 2.5·108 steps; the frame-tracking one prints the same rows as the Python rules every 1000 steps for 3·105 steps; those rules are tested against mstep.

Computed
c/pds.c, py/pds.py, tests/test_pds.py, notes/LAB_NOTES.md
No small DFA closes the tape

One side of the tape abstracted by a DFA, the other kept exactly as a pushdown stack, reachability computed exactly by post* saturation: every DFA with at most 7 states, on either side, lets the abstraction reach a halt. Run-window languages on the tape do not close either. Tested sound on random small machines.

Heuristic
py/blank.py records, notes/LAB_NOTES.md
The tape grows very slowly

The visited width is 199 cells after 106 steps and 642 after 1010, so the time per new cell grows fast, far faster than for the other machines studied here. The left part of the tape holds blocks of 1s of even length separated by single 0s; the head reaches new cells on both sides.

Heuristic
py/macro.py stats, notes/LAB_NOTES.md
Pass endings look like a binary counter

Almost every pass ends at a gap of length 4j + 2, and each j is about half as common as j − 1. In macro terms half of all passes are B passes, which end at their own head gap h = m + 2, where m is the last segment the F pass before crossed; h = 2, 4, 6, 8, … occur with frequencies halving exactly. In the macro machine the first nonzero gap is counted down by 2 per round and a segment just before it becomes a gap of its own size: a counter whose digits are the gaps. Not a proved description of the run.

Heuristic
c/macro.c, notes/LAB_NOTES.md
Only a few odd numbers

Odd numbers are born only at the left end of the tape (proved, above), and the left end is rare: 38 visits in the first 3·106 macro steps. In the run there are at most 4 odd numbers at a time, and F meets two 1s side by side only 546 times in 1010 steps (of 344,806,676 passes).

Heuristic
py/perturb.py, c/twostack.c perturb, notes/LAB_NOTES.md
Stuck configurations next to the run

Changing one to three even numbers of a configuration of the run by 2, with every parity kept, gets the macro machine stuck: 6 of 1,980 tries in Python, 20 of 1,500 in C with longer runs (108 to 109 steps). One example changes a single entry deep in the stack from 0 to 2. So whatever keeps the run from getting stuck depends on exact values, not on parities. Every stuck copy examined ends the same way: a frame created with value 2, a few frames above the end, flipped twice and then hit once more: a third flip, or its own odd countdown running out at value 0.

Heuristic
c/twostack.c, notes/LAB_NOTES.md
The run is no safer than its perturbed copies

Per flip (an R2 step taking 1 from its caller) the run and its perturbed copies agree: 61–63 % of flips hit frames created with value 2, about 1 % are second flips, and the run's near-miss rate (2 in 1,181 flips by 1011 steps) is close to theirs (0.29 % over 124,075 flips). The copies get stuck about once per 6,200 flips (20 of 1,500 copies), so the run would have got stuck by 1011 steps with probability about 0.17. The copies do not relax back to safety (their rate stays flat for 108–109 steps after the change), their risk falls at most slowly with the run's age, and the run's flips do not thin out (about 200 per decade). If the run behaves like its copies, it gets stuck with chance 2 to 3 % per decade of steps: a halt is likely but astronomically late. This is a model, not a proof.

Open
notes/LAB_NOTES.md
The macro machine never gets stuck

A description of where the odd numbers can be that the rules preserve and that excludes the two stuck cases. That would prove the machine never halts. An odd number has over a thousand distinct small neighbourhoods in the run, so the description is not tiny; window and pushdown languages over the macro numbers are the next tries. Any such description has to separate the run from configurations one even number away, which per flip behave like it and do get stuck.

Open
Does it halt from blank tape?

Not known.

Check it yourself

Commands

bash scripts/setup-lean.sh                    # Lean 4.34.0, core only
. /etc/profile.d/lean.sh
bb6-1RB0LF_1RC0LB/lean/check.sh               # the library, then Machine, Blank, Axioms (under a minute)
python3 bb6-1RB0LF_1RC0LB/tests/test_machine.py
bb6-1RB0LF_1RC0LB/lean/check.sh               # also Macro.lean: mstep_sound, no_halt_of_macro
bb6-1RB0LF_1RC0LB/lean/check.sh               # also Parity.lean: even configurations are safe, odd numbers come from the left end
python3 bb6-1RB0LF_1RC0LB/py/blank.py records 100000 60
gcc -O2 -o tmrun tools/c/tmrun.c && ./tmrun 1RB0LF_1RC0LB_1RD1RB_1RE1RF_1LA---_0RC1LA 10000000000
cd tools/py && python3 -m bbtools.invariants 1RB0LF_1RC0LB_1RD1RB_1RE1RF_1LA---_0RC1LA 12
python3 bb6-1RB0LF_1RC0LB/tests/test_passes.py
python3 bb6-1RB0LF_1RC0LB/py/passes.py check 1000000
gcc -O2 -o passes bb6-1RB0LF_1RC0LB/c/passes.c && ./passes 10000000000
python3 bb6-1RB0LF_1RC0LB/tests/test_macro.py
python3 bb6-1RB0LF_1RC0LB/py/macro.py show 40
python3 bb6-1RB0LF_1RC0LB/py/callstack.py check 1000000   # how the counter changes, by kind of step
gcc -O2 -o macro bb6-1RB0LF_1RC0LB/c/macro.c && ./macro 10000000000
python3 bb6-1RB0LF_1RC0LB/tests/test_pds.py
gcc -O2 -o pds bb6-1RB0LF_1RC0LB/c/pds.c && ./pds 6 L && ./pds 6 R   # every DFA up to 6 states, about a minute each
gcc -O3 -o twostack bb6-1RB0LF_1RC0LB/c/twostack.c && ./twostack 10000000000   # about 90 s; TWOSTACK_VERBOSE=1 prints near misses
./twostack perturb 100000000 100000000 40 1   # 200 perturbed copies, 10^8 steps each, about 3 min
python3 bb6-1RB0LF_1RC0LB/tests/test_accel.py
gcc -O3 -o fastrun bb6-1RB0LF_1RC0LB/c/fastrun.c && ./fastrun run 1e12 - state.bin   # about 70 minutes; resumable