Busy Beaver Explorer / 1RB1RA_1RC1LB_1LD0RA_1LB0LE / explained
The machine 1RB1RA_1RC1LB_1LD0RA_1LB0LE, explained
1RB1RA_1RC1LB_1LD0RA_1LB0LE_1LF1LD_---0LD
Nobody knows whether this six-state, two-symbol Turing machine ever halts when started on a blank tape. This page runs it in your browser and walks through what has been found: its run is a sequence of passes, each pass is a map on the lengths of the blocks of ones, the count of ones at each pass start is a multiple of 4, and so a halt could only come from one rare event, a sweep that stops at a block of a single 1.
Every claim carries a tag for what it rests on: Lean, kernel checked by Lean's kernel alone, Lean, native_decide also trusts Lean's compiler, computed by C or Python in the repository, exhaustive but not proved, heuristic sampling or a pattern seen so far. The status panel at the end lists them all, and the proof-status page has the details and theorem names.
The transition table
The machine has states A to F and reads 0 or 1. Each entry says what to write, which way to move, and the next state: 1RB writes 1, moves right, goes to B. The only missing entry is F on a 0, so the machine halts exactly when it is in F reading a 0. F is entered only from E on a 0, which writes a 1 and moves left; so the halt is the pattern 0 E>0: E standing on a 0 with another 0 to its left. Lean, kernel step_none_iff, halt_shape
The entry the simulator below just used is highlighted.
The tape, step by step
Start on a blank tape in state A and step. After 17 steps the tape is 11 0 11 with A on the blank cell right of it: the first pass start Lean, kernel blank_at_17. From then on the head keeps returning to the right end in A, and each time the tape is blocks of ones separated by single 0s. The readout counts these pass starts and shows the block list at the last one. You can also load any block list and run from its pass start.
Space-time diagram: one row per step, newest at the bottom, the whole visited tape across; the head is orange and rows at pass starts are marked on the left in green. Notice the ones count: it moves around inside a pass and is a multiple of 4 at every pass start.
One pass: sweep left, zigzag back
At a pass start the tape is 1^y1 0 1^y2 0 … 0 1^yk A>0, written as the block list [y1, …, yk]. A pass has five phases, and each is a Lean theorem about every tape around it and every block length Lean, kernel (lean/Rules.lean). Lean chains them into the closed form below for every block list (pass, lean/Pass.lean).
- startA, B and C write three ones on the right; C turns D back.start
- sweepD and E run left writing 0 and 1 in turn, halving the block they cross.de_sweep, de_sweep_odd
- crossE meets a 0 between blocks: it writes 1, F writes 0, and D goes on into the next block. If that block is empty (the 0 has a 0 to its left), F reads a 0: halt.e_cross
- stopD meets a 0: it writes 1 and B runs left to the previous 0. The sweep is over.d_stop
- zigzagA, B and C zigzag back to the right end, each round moving a 0 one cell right, until A reaches the blank and the next pass starts.zig, a_sweep, b_sweep
Which blocks the sweep crosses depends only on parities: the last block is crossed if it is odd, then blocks are crossed while they are even, and the sweep stops at the first odd block yj. If every block before the last is even, the sweep runs off the left end into the blank, and the machine halts.
The closed form of the pass map
Writing hi = yi/2 for the crossed even blocks and hk = (yk+5)/2, and reading the blank on the left as empty blocks y0 = y−1 = 0, one pass does this (py/passmap.py):
The page checks the formula against the machine on every pass you load (the line under the tape above). In the repository it agrees with the machine on about 3,100 random block lists heuristic, and its orbit from [2, 2] is exactly the 1,005 pass starts of the first 109 steps computed. Lean proves it for every list (pass, lean/Pass.lean) Lean, kernel.
The passes, one after another
From blank tape the pass starts are [2, 2], [3, 5], [1, 7, 4], [5, 11], [2, 11, 7], …. The picture below runs the machine itself in your browser, draws the tape at each pass start as one row, and compares every row with the closed form.
One row per pass start, the first at the top, each cell of the tape one column (ones dark, crossed blocks of the next sweep green, the stop block orange). The tape grows on both ends, about like the cube root of the step count.
The orbit of the closed form is cheap to follow far. Pick a number of passes; the chart shows the size of the stop block yj on each pass whose sweep crosses blocks (the last block is odd), on a log scale. When the last block is even the sweep stops at once on that even block, which can never be 1. A halt needs that size to be 1 (part 6). In 2·107 passes it never is, and after pass 50 it is never below 59 heuristic.
What the orbit did
Two-block states [a, 2a+d]
Whenever the list has two blocks, the second is about twice the first: d = y2 − 2y1 stays within ±3. Between returns to two blocks a tail block on the right halves each pass.
The count of ones, mod 4
Pass n (counting from 0) starts with exactly 4(n+1) ones: 4, 8, 12, …. That holds for every pass start of the first 109 steps computed, and it follows from the closed form, which adds exactly 4 ones whenever the stop block is not 1:
- Even last block yk = 2m: the block goes (−2m) and two blocks gain m+2 each (+2m+4). Net +4.
- Odd last block, stop at yj > 1: the crossed blocks yj+1, …, yk and yj itself are replaced by sums of halves; adding the formula up gives the same +4 (the page checks it on every pass it runs).
So the count of ones is 0 mod 4 at every pass start of the orbit: Lean proves that a pass adds exactly 4 ones and that pass n from blank tape starts with 4n ones, counting blank tape as pass 0 (next_sum, orbit_ok) Lean, kernel. This is not a conserved quantity of the machine step by step: inside a pass the count wanders (watch the simulator), and a search finds no conserved combination a·ones + b·position + W[state] modulo 2 to 12 computed. It is a statement about pass starts only, and it rests on the closed form, which Lean proves for every block list (pass, lean/Pass.lean) Lean, kernel.
Ones at each pass start of the closed-form orbit (dots) and the line 4(n+1). Every dot sits on the line.
The one way it could halt: a block of 1
Put parts 3 and 5 together. A halt needs the sweep to run off the left end, which happens when the last block is odd and every other block is even. Such a list has an odd number of ones. But at every pass start the count is a multiple of 4, unless something outside the closed form happens. The only case outside it is a sweep that stops at a block of a single 1, where the count changes by an odd amount. So:
This chain is a theorem: halts_only_by_one in lean/Pass.lean proves that if the machine halts from blank tape, some pass of the orbit stops at a block of a single 1 Lean, kernel. Whether that ever happens is open. Nothing in the orbit seen so far comes close: every block the form makes is at least 2 except a new first block, so a stop block of 1 would have to be a first block that halved down about log2(ones) times in a row. Try the examples to see the event and what follows it.
Each row runs the machine itself from that pass start and compares with the closed form where it applies.
What is known, and how
The machine's question is open. The columns keep apart what Lean proves with its kernel alone, what it proves with native_decide, what C or Python in the repository computes, and what is only observed. This panel is built from the same file as the proof-status page (bb6-1RB1RA_1RC1LB_1LD0RA_1LB0LE/status.json), so the two stay in step.
For a readable summary of where the work stands, the failed proof routes and the final reduction, see what is known so far.