Busy Beaver Explorer / 1RB1RF_1LC0LB / explained

An open six-state machine · status as of 2 November 2026

Does this machine ever halt?

1RB1RF_1LC0LB_1RE0LD_1LB0RF_0RA0RC_1RE---

Nobody knows. Started on a blank tape, this Turing machine has run ten billion steps without stopping. The work on it has just begun: this page shows how its tape is organised, the one way it could stop, what has been proved in Lean, what has only been computed, and the patterns that the next proofs will aim at.

KernelOne halting shapeEvery halt from blank tape comes two steps after the head, in state E, reads 0 1 1.
KernelThree sweep rulesSweeps right in E and left in B shift the pairs 10; E marks each boundary 0 10 as 0 11.
Computed1010 stepsNo halt (C simulator). In Lean: 20,000 steps by the kernel, 107 with native_decide.
HeuristicWalls replay the startIn front of a long block the left end goes through the run from blank tape again, and walls nest.
Kernel proved in Lean, checked by the kernel only
native_decide proved in Lean, one evaluation trusts the compiler
Computed C or Python, tested but not proved
Heuristic patterns and evidence
Open not known
1 · The machine

Six states, two symbols, one halting transition

Each entry says what to write, which way to move and which state to enter. The run starts in state A on a blank tape. The only way to stop is to be in F reading a 1.

statereads 0reads 1

Kernel F is entered from A or D reading a 1 and then reads the cell to their right. D is entered only by C reading 1 (0LD), which leaves a 0 just right of D, so D never leads to a halt. A is entered only by E reading 0. So every halt from blank tape comes two steps after E>0 1 1: E steps onto the 0, A onto the first 1, F onto the second.

halt_from_e011, d_right_zero, lean/Blank.lean

The figures beside the table count how often each transition is used in the first million steps of the simulator below: A, E reading 0, D reading 1 and F are rare, and mark the moments where something happens.

2 · Watch it run

The tape from blank, read as pairs

The tape soon consists of pairs 10, in blocks separated by single extra 0s. Below the cells, the tape is read from the left with the words a = 10 and b = 110 and run-length coded, so a^13 0 a^13 is two blocks of 13 pairs. The head is the coloured cell; the diagram underneath stacks one row per turn of the head, so sweeps show as long rows.

Jump to
step 0state Acells 1ones 0

Cells window: 37 cells around the head. Diagram: the whole tape, one row per turn, newest at the bottom (1 = dark, head = orange).

3 · Sweeps and the halt

Shifting pairs, marking boundaries

Three rules carry most of the run. Each is proved in Lean for any number of pairs and any tape around them, from a symbolic run written out by tools/py/bbtools/symtm.py.

So a sweep to the right leaves every boundary it crosses marked as 0 11. In the run, the excursions from the right end that follow run left to a boundary and back, and the marks are gone by the time the head is back at the left end (observed, not proved). A mark that is still there when a sweep in E arrives, in step with E's pairs, is the halt.

Heuristic At all 207 moments up to 1010 steps when the head extends the tape on the left, 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: E arrives on its first 1 and turns back. Right after a boundary it would be the halting shape.

runs/left_1e10.txt

4 · Left-end moments

The tape each time the left end grows

Each row is a moment when the head reaches a new cell on the left, after last reaching one on the right: the step, the width, and the blocks of pairs in order (a b or a double 0 is shown as it is). Shaded rows start with a wall, a block of at least 50 pairs at the left end; rows with a bar replay the run from blank tape in front of the wall (section 5).

stepwidthstatetape as words

From runs/left_1e10.txt, written by tools/c/tokrun (the same as py/blank.py left). The first rows are checked against the simulator on this page by tests/test_explainer.py.

5 · Walls

In front of a wall, the run starts over

Take the run from blank tape at its left-end moments: moment i reads 0^2 P a^x 1, a prefix P and a last block of x pairs. When a moment starts with a wall of W pairs, the moments that follow read 0^2 P a^y 0 … with the same prefixes P, the wall in place of the last block. The wall loses the same amounts each time, whatever W is and whatever lies beyond it. The chart shows what each wall has lost after each replayed moment.

The walls of py/replay.py with at least five replayed moments; the lines lie on top of each other.

Heuristic Ten walls in the first 1010 steps, from 71 to 43,801 pairs, all lose 1, 4, 6, 10, 12, 22, 28, … after their replayed moments (the first, 257 pairs at step 277,787, for 29 moments); that is about half the blank run's last block, plus one. Walls nest: at step 1.78·109 the tape starts 0^2 a^1768 0 a^6 0 a^10762. So the run looks like a recursive counter whose structure changes when a wall is used up. The replay counts are lower bounds, since moments can merge while the left end grows into the wall.

py/replay.py, runs/left_1e10.txt

6 · The counter

The right end counts down in base 3

Look at the tape each time the head comes back to the right end. Read from the right, it is a list of levels, each s (10)^g s′ (10)^W: two single cells s, s′ around a block of g pairs, then a block of W pairs. A level's digit is 2 when its cells read 1 1, 1 for 0 1 and 0 for 0 0. One trip of the head from the right end and back takes one off the number these digits spell in base 3, last level lowest:

  • 2 → 1: s becomes 0, and one pair moves from W into g.
  • 1 → 0: s′ becomes 0, and the lengths stay as they are.
  • 0 → 2 (a borrow): the trip goes on to the next level to the left; on the way back this one gets 1 1, and one pair moves from W into g.

The last level is the exception: its W grows instead of shrinking, so each trip adds two pairs to the tape. A level's W only shrinks, by one pair for every two of its digit's three changes, and lower levels change three times as often as the level to their left. Press the button to step the counter from the tape at step 1010.

trips 0pairs on the tape 0

Left: the irregular blocks at the left end of the tape, as tokens (block lengths and single cells). Right of them, the levels; the last level is on the right. A highlighted number changed on the last trip. The levels and the starting tape are from python3 py/counter.py levels 1e10.

Kernel Each trip from the right end and back acts on the levels as above, for any block lengths and any number of borrows, with whatever lies to the left of the level where the trip turns: counter_last2, counter_last1, counter_borrow2 and counter_borrow1, built from eight symbolic pieces of the run (a walk over a level with digit 0, the turn at a digit 2 or 1, the reset on the way back). The theorems need g and W odd for digit 2 and even for digits 1 and 0, the parities the run keeps.

lean/Counter.lean, lean/Rules.lean

Computed Of the 151,240 trips in the first 1011 steps, 150,680 are covered by these theorems and all of them end as the theorems say. In the other 560 the borrow runs past the levels into the irregular blocks at the left end (321), or meets one of the leftmost levels when it is too short or of the wrong parity (239). Those trips, the top of the counter, are where the walls of section 5 live and where a halt would have to come from.

python3 py/counter.py check 1e11 (the macro simulator tools/py/bbtools/macro.py)

7 · Growth

The width grows like the square root of time

Width (visited cells) at steps 10, 20, 50, … 1010, on logarithmic axes, with the line 2.6√t. Half of the cells are 1. From runs/growth_1e10.txt (c/growth.c). Computed

8 · Next

What would turn the patterns into proofs

Open The top of the counter. The trips that run past the levels into the left end, and those that meet a short leftmost level, as maps on the block lengths: how a new level is made, and what the left end does to a level that runs out.

Open The replay. A statement that in front of a long enough wall the left end follows the blank run, the wall losing a fixed amount per moment. This would make the run a recursion on walls.

Open Wall exhaustion. What happens when a wall is used up, and whether any case leaves a mark right after a boundary in E's way.

Open A language over pairs. Closed tape languages on windows of 2 to 7 raw cells all allow a halt; one built on the words 10, 110, 0, keeping the pair alignment, might not.

9 · Ledger

Every result, by what it rests on

The proof-status page has the same results with the commands to check them, built from bb6-1RB1RF_1LC0LB/status.json; this list is written from the same file by tools/pages/explainer_status.py.