Busy Beaver Explorer / 1RB1RA_1RC1LB / level by level
1RB1RA_1RC1LB, level by level
1RB1RA_1RC1LB_1LD0RA_---0LE_1LC0LF_1RE0LB
This page is about one very small computer program, a six-state Turing machine, and one question about it: if you start it on an empty tape, does it ever stop? Nobody knows yet. People have been asking this question about every machine of this size (the "Busy Beaver" problem), and this machine is one of the few whose answer is still open.
Watching the machine one step at a time tells you almost nothing, because it runs for billions of steps and longer. But if you step back, patterns appear, and each pattern can be described more simply than the one below it. This page climbs that ladder in six levels. Each level is a working simulator you can step through yourself. By level 4, the whole question has turned into a question about one number, N: the machine stops exactly when N becomes a power of two (2, 4, 8, 16, …). Level 5 shows the one part of the run that is completely regular, the right end of the tape, and why it is.
The six levels at a glance
Each level groups many steps of the level below into one step. The numbers on the right say how much happens in the first 1,322,171 steps of the machine, counted at each level (level 5 shows a cycle instead). The higher you go, the fewer steps there are to look at, and the more each step tells you.
- Level 5The last blocks repeatInformation only flows left, so the right end of the tape settles into exact cycles, block by block. The left end, where N is decided, never does.the last block: a cycle of 4
- Level 4The number NThe tape is summed up by one number. The machine stops exactly when N is a power of two.about 120 super steps
- Level 3The halving waveA ripple runs leftward through the blocks, halving as it goes, and turns back at the first odd number.479 waves
- Level 2The macro stepThe tape is a list of numbers (the block lengths), and one rule turns each list into the next.1,000 macro steps
- Level 1Block movesThe tape is made of blocks of 1s, and the head only ever does a handful of things to them.11,475 moves
- Level 0The machineOne cell, one step at a time: read, write, move, change state.1,322,171 steps
How sure are we?
Every level is tagged with how firmly it is known.
- proved A computer-checked proof in the Lean proof assistant shows this holds for every possible case, not just the ones we tried.
- proved, fast check Proved in Lean, but with a faster checking method that also trusts Lean's compiler.
- computed Programs check it on enormous numbers of cases and it has never failed, but there is no proof.
- open Nobody knows.
The write-up states each level precisely, with every proof referenced.
Words used on this page
- tape
- An endless row of cells, each holding 0 or 1. It starts as all 0s.
- head
- The machine's read/write position on the tape, drawn with an orange outline.
- state
- One of six letters, A to F: the machine's "mood", which decides what it does next.
- block
- A run of 1s next to each other. A block of 5 is 11111.
- halt
- Stop. This machine stops only if it is in state D and reads a 0.
- power of two
- 1, 2, 4, 8, 16, 32, … In binary these are a 1 followed only by 0s.
Wherever a level is at a moment early enough to replay, the Show in the machine button runs the plain machine to that same moment, so you can compare the two pictures.
The machine, one cell at a time
A Turing machine is about the simplest computer there is. It has a tape of cells holding 0s and 1s, a head that looks at one cell, and a state, which is one of a few letters. Every step follows the same three moves:
- Look up the current state and the symbol under the head in the table below.
- Write the symbol the table says (0 or 1) into the cell.
- Move one cell left (L) or right (R) and switch to the state the table names.
For example, the very first step: the machine is in state A and reads a 0. The table entry for A and 0 is 1RB: write a 1, move right, switch to state B.
The table has one entry with no instruction: D reading 0. That is the only way to stop. So the whole question is whether the machine ever reaches state D while looking at a 0.
Try this: press Step a few times and watch the table highlight the entry being used. Then press +1,000 a few times and watch the picture under the tape. That picture stacks the last 200 tapes on top of each other, oldest at the top, so the head's path draws a line. You will see long diagonal sweeps across the whole tape, and short zig-zags where the head shuttles back and forth over one stretch. Those two shapes are what level 1 is about.
proved The machine does not stop in its first 20,000 steps. proved, fast check Nor in its first 10,000,000.
The table
Rows are states, columns are the symbol read. 1RB means write 1, move Right, go to state B. The highlighted entry is the one the next step will use.
The tape around the head
The last 200 tapes, oldest at the top, one row per step; the orange mark is the head. Showing the whole tape.
Blocks of 1s, and a few moves that change them
provedAfter its first 15 steps, the tape always looks the same way: blocks of 1s with short gaps of 0s between them. So instead of drawing every cell, we can draw each block as one rounded bar labelled with its length, and each 0 in a gap as a dot. The head is still the orange outlined cell.
111 0 11111 000 11 with the head in state A at the start of the middle block. As blocks: a block of 3, one 0, the head's block of 5, three 0s, a block of 2.Seen this way, the head turns out to do only three kinds of thing, shown in the gallery below with real before-and-after pictures:
- Transfer. The head, in state A, sits at the start of a block. It runs across the block and back, and in doing so moves two cells out of it: one cell to the block on its left, and one to the first block on its right. The block shrinks by 2.
- Sweep right. When the head's block has been used up completely, the head runs all the way to the right end of the tape, closing up the double gaps as it goes.
- Carry left. When exactly one cell is left, the head (now in state F) heads left instead. Every block of exactly 2 that it meets gets swallowed. The first block that is not 2 stops it. If every block to its left is 2, it swallows them all, runs off the left end, and the machine stops. That is the only way this machine ever halts.
In the proofs, these three kinds of thing are split into seven precisely stated moves (the names in the box below, like transfer and carry_two), plus a starting move for the first 15 steps. Each one is proved to work for blocks of any length, with an exact count of how many machine steps it takes.
Try this: press Next move and read the box Last move: it names the move, shows its pattern (A> means "the head, in state A, is on the next cell"), and gives its step count. The line bare machine at this step shows a ✓ when the plain level-0 machine, run to the same step, has exactly the same tape.
proved in Lean, for every block length and whatever else is on the tape (lean/Rules.lean).
Last move
Moves so far (newest first)
The macro step: the tape as a list of numbers
provedSince the tape is just blocks, it is completely described by their lengths. At the start of each round of transfers we write it as three things:
ls: the blocks to the left of the head, listed from the nearest one outward;n: the length of the block the head is on;cs: the blocks to the right, listed from the nearest one outward.
We write this as X(ls, n, cs). For example, here is X([4, 1], 6, [2, 3]):
One macro step takes you from one X to the next. It always goes the same way, and the only thing that decides which way it goes is whether n is even or odd:
This is a big simplification. Instead of a tape with millions of cells, the machine is now a rule that turns one short list of numbers into another, and Lean proves that this rule matches the machine exactly, including how many steps each macro step takes. Lean also proves that the machine halts if and only if this list rule eventually hits the halting branch: n odd, and every block on the left equal to 2 after the transfers.
Try this: press Next macro step a few times and read The next macro step, which spells out what is about to happen, and Distance from halting, which counts how many blocks on the left are already 2. Then press +1,000 and see how far from halting it is: the blocks on the left grow into the hundreds and thousands, nowhere near all 2s. To watch a halt, use the inputs at the bottom: ls = 2, 2, 2, n = 1, cs = 3, then Start here and Next macro step.
proved in Lean: the list rule matches the machine (next_sound), and the machine halts exactly when the list rule does (halts_iff). Running the list rule, Lean also proves there is no halt in the first 20 billion steps.
The next macro step
Distance from halting
The halving wave
computedLevel 2 still takes a lot of macro steps to see anything happen. Level 3 looks at the same run from a different angle, and finds a single shape behind it: a wave.
Take a snapshot each time the head, in state A, has just arrived at the right end of the tape. Call that moment an event. At every event the tape is simply blocks separated by single 0s. Between one event and the next, the head makes a trip leftward into the tape and back. That trip behaves like a wave carrying a number, which we call c:
- The wave starts at the last block:
c= (length of the last block) − 1. - If
cis even, the wave moves on to the next block to the left. Its new value is that block's length + c/2 − 2. Half ofcis carried over, which is where the "halving" comes from. - If
cis odd, the wave turns around, and the head sweeps back to the right end. That is the next event. - If the wave gets past the first block, it is on empty tape (block length 0), and it keeps halving there:
c → c/2 − 2. If it ever gets down to exactly 0, the machine halts. That happens when the wave arrives withc + 4equal to a power of two.
One special case: if the last block is empty, there is no wave. The tape just gains a block of 2 at its right end.
| block | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| length | 1 | 4 | 3 | 6 | 8 | 14 | 8 | 1 |
| wave c | 15 | 6 | 0 | |||||
| how | 14 + 6/2 − 2 = 15: odd, turn | 8 + 0/2 − 2 = 6: even, go on | 1 − 1 = 0: even, go on |
This explains a puzzle from level 0: why the head so rarely reaches the far left of the tape. To get there, the wave has to find an even number at every single block, all the way down. With dozens of blocks, that is like flipping a coin dozens of times and getting heads every time. So most waves turn back after a block or two, and visits to the left end get rarer and rarer: the head reaches new tape on the left at step 2,047,931, and then not again until step 26,618,972,322.
Try this: press Next event and look at the table: each column is a block, and the green row shows the wave's value at each block it reaches, with an outline where it turns. Then press To the next visit to the left end to jump to the next time the wave makes it all the way, and see how far apart these visits are.
computed This description was found by studying the run, and is checked against the plain machine at every event in the first billion steps, with exact step counts. Lean proves it four events at a time (that is level 4), but not one event at a time.
One number decides it all
provedOne more pattern: every fourth event, the tape ends in the same way, with a block of 5 and then an empty block. So at those moments the tape is a list P = [p1, …, pm] followed by 5 and 0, and four waves later it is again such a list, P'. Going from P to P' is one super step, and it can be worked out with simple arithmetic.
Step 1: the wave values d. Start at the right with d = 20, and work leftward: each block's value is its length plus half the value to its right. Stop at the first odd value: that is where the wave turns.
Step 2: the new list P'. Every block the wave passed becomes half its d. The block where it turned becomes (d + 5) ÷ 2. The block just left of that gains (d − 1) ÷ 2. Blocks further left are untouched.
| block | 1 | 2 | 3 | 4 | 5 | 6 | end |
|---|---|---|---|---|---|---|---|
| p (length) | 1 | 4 | 3 | 6 | 17 | 12 | 5, 0 |
| d | · | · | 3 + 20/2 = 13 | 6 + 28/2 = 20 | 17 + 22/2 = 28 | 12 + 20/2 = 22 | 20 |
| P' | 1 | 4 + 6 = 10 | (13 + 5)/2 = 9 | 20/2 = 10 | 28/2 = 14 | 22/2 = 11 | 5, 0 |
The key observation. "Halve and add, and stop at the first odd number" is exactly what happens when you read the list as one big binary number. Treat each block as a digit in binary, with the last block as the units, and add 10:
N = 10 + pm + 2·pm−1 + 4·pm−2 + 8·pm−3 + …
For the example above, N = 10 + 12 + 2·17 + 4·6 + 8·3 + 16·4 + 32·1 = 200, which is 11001000 in binary. It ends in three 0s, and the wave went 3 + 1 = 4 blocks deep. That is true in general:
- The wave goes (number of 0s at the end of N in binary) + 1 blocks deep.
- So it reaches the left end only when N ends in at least
m − 1zeros, wheremis the number of blocks. With 30 blocks, that is like flipping a coin and getting 29 heads in a row. - And the machine halts if and only if N is a power of two, which in binary is a single 1 followed by nothing but 0s.
So the whole question, "does this machine ever stop?", has become: as the super steps go on, does N ever land exactly on a power of two? N is already above 1020 and keeps growing. Powers of two are very sparse among numbers that size, which is why it almost certainly never happens. But nobody has a proof, and questions like this one, about whether a simple number sequence ever hits a target, are famously hard (the Collatz problem is one).
Try this: press Next super step and compare the table with the steps above: the d row is computed right to left, the turn is outlined, and the P' row shows the new list under the blocks it came from. The N panel shows N in binary with its trailing zeros in green, and the bar shows how close they come to reaching the left end. The chart below tracks how deep each wave went (bars) against the number of blocks (line). A bar only touches the line when the wave reaches the left end. Press To the next visit to the left end to see one. To see a halt, type 1, 4 in the box at the bottom and press Start here: N = 10 + 4 + 2·1 = 16, a power of two.
proved Lean proves the super step for every list, and that the machine halts if and only if N is a power of two at some super step (halts_iff_pow2'; the write-up explains the argument). The machine step counts shown here are computed, not proved. open Whether N ever is a power of two.
N
This super step
N written out as a binary sum of the blocks
The last blocks repeat
provedcomputedRun level 4 for a while and watch the right end of the list. The last block only ever takes the values 12, 11, 13, 14, over and over. The last two blocks repeat every 8 super steps, the last three every 32. The tape as a whole never repeats, because it keeps growing on the left, but its right end settles into exact cycles. This level shows why.
Information only flows left. The head sweeps back and forth across the tape, but look at what one super step does to one block. Something arrives from its right, a wave carrying a number h. The last block always gets h = 10 (half of the 20 that level 4 starts from). A block of length p adds it up, d = p + h, and then:
- if
dis even, the block becomes d/2 and the wave goes on to the left with h = d/2; - if
dis odd, the block becomes (d + 5)/2, the block on its left gains (d − 1)/2, and the super step is over.
This is level 4's rule, read one block at a time. Nothing is ever sent to the right. So a block's next value depends only on itself and on what comes from its right, and the last k blocks run as a small machine of their own, whatever the rest of the tape does.
| last block p | 12 | 11 | 13 | 14 | 12 again |
|---|---|---|---|---|---|
| d = p + 10 | 22 | 21 | 23 | 24 | |
| new p | 22/2 = 11 | (21 + 5)/2 = 13 | (23 + 5)/2 = 14 | 24/2 = 12 | |
| sent left | wave, h = 11 | add 10 | add 11 | wave, h = 12 |
Why every level repeats. The same argument climbs from the right, one block at a time.
- The last block gets the same input every super step, so it cycles (above).
- The next block gets the output of that cycle, which repeats. The adds push it up, but by a bounded amount per cycle, and every wave roughly halves it. So it stays below a fixed bound, and once the last block is in its cycle the pair has only finitely many states. It repeats too, here every 8 super steps.
- Each further block works the same way, on top of the cycle of the blocks to its right. Its period is the one below times a whole number. So far that number has always been 1, 2, 4 or 5.
One thing could break the chain: a cycle that sends no wave at all to the left, only adds. The next block would then only grow, never repeat, and pass nothing further on. But then no wave would ever again reach the left end of the tape, so the machine would never halt. So each level either cycles, or the machine never halts. That has not happened in any level checked so far.
Try this: choose how many blocks to watch and press Run until they repeat. The table lists the last few super steps, one per row, with the blocks in tape order (the last block on the right). A green cell passed the wave on, an outlined one turned it, a + marks a block that received an add, and the first column shows what left the group. Rows with the same values as the current one are marked. Then press Jump one period: the blocks come back exactly, while the rest of the tape, and with it N, has moved on.
proved Lean proves that the last k blocks run on their own, and that for every k they either cycle or stop sending anything left, which means no halt (cycles_or_never_halts). It also checks that the last 1 to 6 blocks really do cycle on this run, from super steps 3, 7, 11, 31, 60 and 163, with periods 4, 8, 32, 128, 256 and 1,024 (cycle₁ to cycle₆), and the least periods of the last 1 to 35 blocks, by tables checked in pieces (cycle1 to cycle35). computed The cycles of the last 36 to 44 blocks, found by program. open None of this decides the question: the left end, where N is decided, never settles.
The leftmost watched block, over one period
Find the cycle first.
The periods, block by block
Each further block multiplies the period by this much. proved for the last 6, computed up to 44 (c/superrun.c).