Busy Beaver Explorer / 1RB1RF_1LC0LB

What is known about 1RB1RF_1LC0LB, and what is open

1RB1RF_1LC0LB_1RE0LD_1LB0RF_0RA0RC_1RE---

Nobody knows whether this six-state, two-symbol Turing machine halts when started on a blank tape. This page tracks what has been established about it, sorted by what each result rests on.

The machine is set up in Lean on the shared library and simulated in Python and C. The tape is made of pairs 10 in blocks separated by single cells; sweeps to the right and to the left shift the pairs by one cell, and a sweep to the right marks each block boundary it crosses. Lean proves the halting shape, the sweep rules, and that the right end of the tape is a base-3 counter: each trip of the head from the right end and back subtracts one from a number written in the separator cells, moving one pair between two blocks of each level it changes. The top of the counter, where a borrow reaches the irregular blocks at the left end, is proved shape by shape: every trip of the first 1012 steps is an instance of a Lean theorem, including the trips that build a wall by copying a level into a new first block, a loop proved by induction. What is not proved is that the shapes go on closing up forever; there the run looks like a recursion on long blocks (walls) in front of which the left end repeats the run from blank tape. The explainer runs the machine and the counter in the browser.

Status as of 16 November 2026.

In short

The question is open. Lean proves no halt in the first 20,000 steps by the kernel alone and in the first 107 steps with native_decide; the C simulator finds no halt in the first 1010 steps. These are floors, not the way to an answer.

Where a halt would come from. The only halting transition is F reading 1. Lean proves that in the run from blank tape every halt comes two steps after the head, in state E, reads 0 1 1. A sweep to the right in E crosses each block boundary 0 10 by marking it 0 11; so the machine halts exactly if a sweep in E meets a mark that an earlier sweep left and nothing has cleared, in step with E's pairs. Whether that can happen is the question. Lean proves that no trip of the right-end counter halts (section on the counter below), so a halt can only come from the top of the counter, the trips that reach the left end.

What each result rests on

kernel checked by Lean's kernel alone native evaluated by compiled code trusted C or Python in the repository, exhaustive heuristic sampling, extrapolation, patterns open not known

kernel Proved in Lean, kernel-checked

The halting configurations

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

step_none_iff, halt_shape, lean/Blank.lean

Every halt comes from E reading 0 1 1

F is entered from A or D reading 1 and then reads the cell to their right. D is entered only by C1 → 0LD, which leaves a 0 to D's right, so the D route never halts (d_right_zero); A is entered only by E0 → 0RA. So in the run from blank tape every halt happens two ordinary steps after a configuration E>0 1 1, and the machine halts from blank tape only if E>0 1 1 occurs.

d_right_zero, a_entry, f_entry, halt_from_e011, halts_imp_e011, lean/Blank.lean

The sweep rules

E runs right over any number of pairs 10, shifting each one cell to the right, 2 steps a pair (e_run). E at a block boundary 0 10 turns it into 0 11 in 3 steps and goes on (e_mark). B runs left over pairs two at a time, shifting each one cell to the right, 4 steps per two pairs, through D in between (b_run). All three hold for every number of pairs and any tape around them; the proofs were written by tools/py/bbtools/symtm.py from symbolic runs.

e_run, e_mark, b_run, lean/Rules.lean (generated by lean/rules.py)

The right end is a base-3 counter

When the head is back at the right end (state C reading the 0 of 0 10, blank beyond), read the tape from the right as levels s (10)^g s′ (10)^W, with digit 2 for seps 1 1, 1 for 0 1 and 0 for 0 0. The machine returns to the right end after subtracting one from the base-3 number the digits spell (last level lowest): a digit 2 becomes 1 (s → 0, one pair from W to g), a digit 1 becomes 0 (s′ → 0), and each digit 0 passed by the borrow becomes 2 (one pair from W to g), except that the last level's W grows, by 1 or 2. Proved for every block length (g, W odd for digit 2, even otherwise, W at least 1 to 4 pairs), any number of borrows and any tape left of the level where the trip turns, so no such trip halts. The proofs chain eight symbolic pieces of the run, generated by symtm.py, by induction on the number of borrows.

counter_last2, counter_last1, counter_borrow2, counter_borrow1, lean/Counter.lean; pieces first0, walk0, turn2, turn1, sweep0, sweepLast, last2, last1 in lean/Rules.lean

23 shapes, 7 families and the wall trips of the top of the counter

A trip that the four counter theorems do not cover is the counter's walk over digit-0 levels, then a top piece on the tape left of them, then the counter's sweep back; or, when the last level itself is irregular, one piece that is the whole trip. Lean proves that the walk and the sweep work around any piece that starts in the walk's phase and ends in the sweep's (counter_borrow_any), and proves 23 pieces, each a map on block lengths valid for every value of its variables: for example 0^inf (2x+1) 1 (2y+1) 0 (2z+2) → 0^inf 2x 1 (2y+3) 1 (2z+3) (a borrow into the first level), 0^inf (2x+2) → 0^inf 3 1 (2x+3) (a new level at the left end) and L 1 2x → L 0 (2x+2) (a level of the wrong parity, any tape L to its left). It also proves 7 families of pieces, each with a list of blocks of any length and any values, by induction on the list: the ladders 0^inf (1010)^x [1 10 10 (1010)^a]^ts 1 10 10 10 …, for example, with any number of rungs, which were 15 separate shapes. Together with the walked levels, any number of them, each is the whole trip from the right end and back. The trips that build a wall (next claim) are proved for any list of blocks in front of the copied level: before each copy round the head converts the blocks next to the level with zig-zags that carry a state from block to block, so a round is computed the way the machine walks it, as modes crossing blocks and pieces of tape (py/rework.py, 94 cases, each a symbolic run); Lean proves by induction that the machine does what that function says for any list, then all rounds by induction, and the whole trip with counter_borrow_ex, the borrow theorem with the piece's step count allowed to depend on the tape. That replaced 32 of the 34 wall shapes; 2 of the 23 pieces still build a wall, their runs symbolic stretches chained with the copy loop. The pieces were found and generalised by py/top.py and proved along symbolic runs written by symtm.py; no trip through them halts.

top_0 to top_22 (with the runs top_piece_i, and top_piece_i_k for the stretches of a wall piece), lean/Top.lean and lean/TopWall1.lean (generated by lean/top_gen.py from lean/top_shapes.txt); fam_0 to fam_6, lean/TopFam.lean (from lean/top_families.txt, found by py/family.py), with seqL, seqR, lean/Seq.lean; counter_borrow_any, lean/Counter.lean; counter_borrow_ex, lean/Wall.lean; wall_turn, wall_last, iter_ok, rw_ok, lean/Rework.lean (generated by lean/rework_gen.py from lean/rework_cases.txt), Sys.go_ok, lean/ReworkCore.lean

The copy loop that builds a wall

When the walk meets a level 0 (10)^X with a single pair to its left, the head shuttles between the left end and that level. At the start of each round the tape right of the head (in C at the left end, blank to its left) is 0 (10)^(2a+1) 0 (10)^(2t1+2) … 0 (10)^(2tm+2) 0 0 (10)^X R. One round turns it into the same with a+1 and X−1 (wall_round), for every a, every list of blocks ti, every X ≥ 1 and any tape R; by induction the whole loop copies the level into the first block, (10)^(2a+1) → (10)^(2a+2X+1) (wall_loop, wall_jump). A round is five symbolic pieces (the left end, a block crossed right and marked, the turn at the level, a block crossed back and unmarked, the left end again) chained by induction on the list of blocks.

wall_round, wall_loop, wall_jump, lean/Wall.lean; pieces wall_start, wall_right, wall_turn, wall_left, wall_end in lean/Rules.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 18 the tape is 1 0 1 0 1 0 1 F>0 (blank_at_18).

blank_runs_20000, blank_at_18, lean/Blank.lean

A first run 4 cells longer changes nothing else, for every way of entering it

In the table of 32883 the head can step onto the last cell of the first run of the tape in five states, on a 0 or a 1. For each of these ten entries the outcome for a run of n + 4 cells is the outcome for n cells with one more copy of a 4-cell word: same exit state, same cells left behind. Proved for every bounce with any tape further left, and for every sweep with n = 4a + 5 to 4a + 8, all a. It holds for the three sister machines after renaming the states (and mirroring).

holdouts/1RB0RA_1LC0RE_0LD0LB_1LA1LF_1RA0LF_1LC---/lean/Shift4.lean (generated by py/shift4.py)

One halting question for four machines, given one condition

Two tapes that differ only by k periods 1010 at the left end, just left of the leftmost 1, make the same moves until the head steps onto that leftmost 1; there the head crosses the extra periods and comes back with the same cells if it is in C or D, and both runs halt if it is in F (for every k). After 2, 11, 26 and 50 steps the table started in D, A, B and E is at the same configuration with 0, 1, 2 and 3 periods more. With the renamings and the mirror proved as well: if in the run of 1RB1RF_1LC0LB_1RE0LD_1LB0RF_0RA0RC_1RE--- the head never reads a 1 in state B or C with only 0s to its right, then 1RB0RA_1LC0RE_0LD0LB_1LA1LF_1RA0LF_1LC---, 1RB0LE_0RC0RA_1RD1RF_1LA0LD_1LD0RF_1RB--- and 1RB0LF_1RC0RB_1LD0RA_0LE0LC_1LB1LF_1LD--- each halt if and only if it does (one_question). On the condition for the run of 1RB0RA_1LC0RE_0LD0LB_1LA1LF_1RA0LF_1LC--- itself, the other two follow it (three_questions). The condition says that the first run never gets shorter than 4 cells; it is not proved.

holdouts/1RB0RA_1LC0RE_0LD0LB_1LA1LF_1RA0LF_1LC---/lean/Lockstep.lean, generated part lean/FarEnd.lean (py/farend.py)

native Proved in Lean with native_decide

No halt in the first 10,000,000 steps

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

blank_runs_10M, lean/Blank.lean

trusted Computed, not proved

No halt in the first 1010 steps

The C simulator tools/c/tmrun.c (tested against the Python reference simulator) runs 1010 steps from blank tape without a halt, in under a minute. At that point 258,671 cells are visited and 129,335 of them are 1.

tools/c/tmrun.c; c/growth.c, runs/growth_1e10.txt

No halt in the first 1033 steps

py/accel.py applies the counter trips in closed form, many at once with their exact step counts (each trip costs a linear function of the lengths it touches, from the pieces in lean/Rules.lean), and runs the other trips on the macro simulator, jumping over repeated cycles inside them with rules proved symbolically by tools/py/bbtools/cycles.py. It passes 1.06·1023 steps (1.2·1011 trips) without a halt in 17 minutes, and 1.48·1033 steps (7.2·1015 trips) in two hours. Every state it passes through agrees with the plain macro run, checked to 1014 steps.

python3 py/accel.py 1e23; tests/test_machine.py (TestAccel)

Almost every trip in the first 1012 steps is a counter step

Of the 284,506 trips from the right end and back in the first 1012 steps, 283,803 are covered by the counter theorems and all end as they say (to 1011: 150,680 of 151,240). The other 703 are the top of the counter: 397 borrow past the levels into the irregular blocks at the left end, and 306 meet one of the leftmost few levels when it is too short or of the wrong parity for the theorems. Run with the macro simulator tools/py/bbtools/macro.py (blocks of 4 cells, runs crossed at once; tested cell for cell against the reference simulator), 1012 steps in about six minutes.

python3 py/counter.py check 1e12; tests/test_machine.py checks the first 108 steps

Every top trip to 1012 steps is a proved shape, family or wall trip

Of the 703 trips in the first 1012 steps that the counter theorems do not cover, 114 are instances of the 7 families (their piece, read as blocks and separators, is the family's start with some list of blocks), 75 are wall trips of Rework.lean (the list of blocks in front of the copied level read off the piece, the end computed by the round function the theorem is about) and the other 514 go through the 23 shapes; each ends as its family, wall trip or shape says (comparing tapes with the run, cell by cell). For the two wall shapes the symbolic run jumps over the copy loop with wall_jump (py/wall.py). So every trip from the right end and back in the first 1012 steps is an instance of a kernel-checked theorem; what is computed is only that the run's trips are those instances.

python3 py/top.py check 1e12 (with py/family.py, py/rework.py); tests/test_machine.py checks the first 109 steps and runs each shape and each family (lists of 0 to 4 blocks) on the reference simulator; py/rework.py check runs the round function on random lists and the wall shapes on the plain simulator

No simple conserved quantity

No quantity a·(number of 1s) + b·(head position) + W[state] is conserved modulo m for any m from 2 to 12, so no such count rules out halting candidates, unlike the mod-3 invariant of the holdout.

python3 -m bbtools.invariants (tools/py/bbtools/invariants.py)

Windows of cells do not separate the halt

Closed tape languages built from windows of 2 to 7 cells (tools/py/bbtools/ctl.py) all cover the run and all still allow a halt, so they prove nothing here. The protection seems to be the alignment of the pairs 10 with E's sweep, which windows of raw cells do not record.

python3 -m bbtools.ctl MACHINE K, K = 2..7

Size of the tape description (family screen)

At the 8 records between 2.6·108 and 1.7·1010 steps (first new leftmost or rightmost cell after each threshold 106·4^k) the tape has 39,174 to 337,949 visited cells and compresses to 20 to 27 level-2 tokens (repeats of a word of at most 40 cells, then repeats of groups of such tokens).

python3 holdouts/1RB0LC_0RC0RF_1RD0LE_1LA1RA_1LC1RB_0RB---/screen/screen.py 1RB1RF_1LC0LB_1RE0LD_1LB0RF_0RA0RC_1RE---, saved in screen.json next to it

Four machines, one run shifted (checked to 2·1012 steps)

The holdouts 32883, 40600, 103746 and 131976 are one table started in four states. Compared at the starts of their trips, the four runs from blank tape have the same list of run lengths except for the first run, which differs by a constant (r, r + 4, r + 8, r + 12), at every one of the first 527,004 trips, up to 2·1012 steps. This is a computation; it does not show that the four halt together.

holdouts/1RB0RA_1LC0RE_0LD0LB_1LA1LF_1RA0LF_1LC---/py/lockstep.py, lockstep_2e12.txt next to it

The condition holds in the first 1014 steps

No configuration excluded by the condition of one_question occurs in the first 1011 steps of the run (plain cell simulator), nor in the first 1014 steps of that run and of the run of 1RB0RA_1LC0RE_0LD0LB_1LA1LF_1RA0LF_1LC--- (exact run-length simulator). Proving it needs the theory of the transfers: a bounce takes a cell off the first run and the next entry sweeps it, except at the end of a transfer that moves the second run.

holdouts/1RB0RA_1LC0RE_0LD0LB_1LA1LF_1RA0LF_1LC---/c/good.c, py/goodrun.py

heuristic Evidence only

The tape is blocks of pairs, and grows like the square root of time

Each time the head reaches a new cell at the left end, the tape reads 0 0 (10)^n1 0 (10)^n2 … 0 (10)^nk 1, sometimes with a word 110 right after a block. Through 1010 steps the width is about 2.6√t at step t and half of the cells are 1. The head goes back and forth between the right end and the block boundaries; each sweep to the right in E marks the boundaries, and each excursion from the right end runs left to a boundary and back.

py/blank.py left, py/blank.py turns, tools/c/tokrun.c, runs/left_1e10.txt, runs/growth_1e10.txt

A mark never sits after a boundary at the left-end moments

In all 207 left-end moments up to 1010 steps, the word 110 occurs 67 times, always right after a block of pairs and never right after a boundary 0. Right after a pair it is out of step with E's sweep (E arrives on its first 1 and turns), so it is harmless; right after a boundary it would be the halting shape.

runs/left_1e10.txt; notes/LAB_NOTES.md, 2 November 2026

In front of a long block, the left end replays the run from blank tape

When the tape at a left-end moment starts 0 0 (10)^W 0 with W large (a wall), the following left-end moments repeat those of the run from blank tape, the blank run's last block replaced by the wall, and the wall shrinks by the same amounts every time: 1, 3, 2, 4, 2, 10, 6, 10, 6, 2, 6, 12, … whether W is 71, 257, 1,547 or 43,801. The first wall, 257 pairs at step 277,787, is followed by 29 replayed moments. Walls nest (at step 1.8·109 the tape starts with walls of 1,768 and 10,762 pairs), so the run looks like a recursive counter. The count of replayed moments is a lower bound: the moments are taken where the head extends the tape on the left after extending it on the right, which the replay need not keep in step.

py/replay.py on runs/left_1e10.txt

Proposed family: F06, block-list counters

The description grows slowly: 20 to 27 level-2 tokens at every record from 2.6·108 to 1.7·1010 steps, and 14 to 46 runs in the macro simulator (blocks of 4 cells) at the sampled records from 106 to 1017 steps. Three holdouts share this machine's table from other start states (1RB0LE_0RC0RA_1RD1RF_1LA0LD_1LD0RF_1RB---, 1RB0LF_1RC0RB_1LD0RA_0LE0LC_1LB1LF_1LD---, 1RB0RA_1LC0RE_0LD0LB_1LA1LF_1RA0LF_1LC---). On the screen the four runs show the same list of blocks at the same moments: near step 6.4·107 blocks of 3, 1,546, 39, 1,753, 117, 1,467 and 997 pairs and a last block of 4,405, 4,409, 4,411 and 4,407 pairs. An observation at the sampled records, not a proof that the runs correspond. The base-3 counter on the separators is proved in Lean for this machine. A list of blocks counted in base 3, with walls, is F06.

the README, section “Family screen”

open Open

The top as a whole

Whether the shapes close up into a recursion that can be followed forever. The plain shapes that differ only in how many blocks they cross are merged into 7 families proved by induction on the list, so longer members of those families need no new shape; the wall trips are proved for any list of blocks by induction on the rounds, carrying the head's state from block to block; 2 wall shapes remain, whose trips need cases the round function does not have yet. Then whether any of them can leave a mark right after a boundary in E's way.

next steps, notes/LAB_NOTES.md

Check it yourself

bash scripts/setup-lean.sh                    # Lean 4.34.0, core only
. /etc/profile.d/lean.sh
bb6-1RB1RF_1LC0LB/lean/check.sh               # the library, then Machine, Blank, Rules, Counter, Wall, Top, TopFam, Rework, Axioms
python3 bb6-1RB1RF_1LC0LB/tests/test_machine.py
python3 bb6-1RB1RF_1LC0LB/py/counter.py check 1e10    # trips of the right-end counter; levels / events
python3 bb6-1RB1RF_1LC0LB/py/accel.py 1e23          # counter trips in closed form, the rest on the macro simulator with cycle jumps
python3 bb6-1RB1RF_1LC0LB/py/blank.py left 3000000 40
gcc -O2 -o tmrun tools/c/tmrun.c && ./tmrun 1RB1RF_1LC0LB_1RE0LD_1LB0RF_0RA0RC_1RE--- 10000000000
gcc -O2 -o tokrun tools/c/tokrun.c && ./tokrun 1RB1RF_1LC0LB_1RE0LD_1LB0RF_0RA0RC_1RE--- 10000000000 a=10,b=110 L 1000 > left.txt && python3 bb6-1RB1RF_1LC0LB/py/replay.py left.txt
cd tools/py && python3 -m bbtools.invariants 1RB1RF_1LC0LB_1RE0LD_1LB0RF_0RA0RC_1RE--- 12
cd tools/py && python3 -m bbtools.ctl 1RB1RF_1LC0LB_1RE0LD_1LB0RF_0RA0RC_1RE--- 5