Busy Beaver Explorer / 1RB1RF_1LC0LB / explained
An open six-state machine · status as of 2 November 20261RB1RF_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.
0 1 1.10; E marks each boundary 0 10 as 0 11.native_decide.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.
| state | reads 0 | reads 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.
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.
Cells window: 37 cells around the head. Diagram: the whole tape, one row per turn, newest at the bottom (1 = dark, head = orange).
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
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).
| step | width | state | tape 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.
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
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:
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.
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)
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
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.
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.