Busy Beaver Explorer / 1RB0LF_1RC0LB / explained
A 6-state Busy Beaver machine ยท Status as of 6 November 2026.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.
D>0 1The one way to stop: D reads a 0 with a 1 to its right.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 >.
| state | reads 0 | reads 1 |
|---|---|---|
| A | 1 R B | 0 L F |
| B | 1 R C | 0 L B |
| C | 1 R D | 1 R B |
| D | 1 R E | 1 R F |
| E | 1 L A | halt |
| F | 0 R C | 1 L A |
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.
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.
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.
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.
Status as of 6 November 2026. The same list as the proof-status page, built from the same file.
step_none_iff, halt_shape, lean/Blank.leanThe 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.
blank_runs_20000, blank_at_63, lean/Blank.leanThe 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).
pass, pass_outcome, start_F, start_B, lean/Pass.leanA 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.
sweep, sweep_end_odd, sweep_end_even, erase, erase_end, lean/Pass.leanA 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.
mstep_sound, blank_to_M0, no_halt_of_macro, lean/Macro.leanAt 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.
phi_interior, phi_end, phi_bottom, lean/Counter.leanRead 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.
even_not_stuck, even_step, even_run, oddc_le, oddc_run, lean/Parity.leanIf 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.
blank_runs_10M, lean/Blank.leanThe same run for 107 steps, evaluated by compiled code.
macro_runs_100M, blank_runs_macro_100M, mok_iff, lean/MacroRun.leanCompiled 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).
tools/c/tmrun.c, tests/test_machine.pyThe 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).
tools/py/bbtools/invariants.pyNo 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.
c/passes.c, py/passes.py check, tests/test_passes.pyIn 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).
c/macro.c, py/macro.py check, tests/test_macro.pyRun 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.
c/fastrun.c, c/twostack.c, py/accel.py, tests/test_accel.py, tests/test_macro.pyThe 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.
c/pds.c, py/pds.py, tests/test_pds.py, notes/LAB_NOTES.mdOne 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.
py/blank.py records, notes/LAB_NOTES.mdThe 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.
py/macro.py stats, notes/LAB_NOTES.mdAlmost 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.
c/macro.c, notes/LAB_NOTES.mdOdd 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).
py/perturb.py, c/twostack.c perturb, notes/LAB_NOTES.mdChanging 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.
c/twostack.c, notes/LAB_NOTES.mdPer 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.
notes/LAB_NOTES.mdA 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.
Not known.
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