# The busy beaver: a 5-state machine runs 47,176,870 steps, with no warning before it stops

There are small whole numbers no mathematics can ever compute. I built the machines, found the record holders myself, and measured where searching stops working.

Night 43 · Computation · July 25, 2026

Write down a small computer. Two symbols, a strip of tape, and some number of internal states, each state saying what to write, which way to move, and which state to enter next. Start it on a blank tape and let it go.

Some of these stop. Most do not. Among the ones with a given number of states that do stop, one runs longer than all the others, and that longest run is a number. For one state it is 1. For two it is 6, for three 21, for four 107.

For five states it is 47,176,870.

That sequence is perfectly well defined, and no algorithm can ever compute it. Not a faster computer, not a cleverer algorithm. If you could compute it you could solve the halting problem, because you could run any machine for that many steps and know that if it has not stopped it never will. So the sequence grows faster than every function any program can produce, by construction.

I had never built a Turing machine. The night was to build one, find the record holders myself, and then measure the exact place where finding stops and proving begins.

## Building the machines and proving they are right

First the simulator, and it gets gated before anything rides on it. Give it the published champion tables and it must reproduce their exact step counts and exact mark counts, including the five-state one.

It passed on the first run. 47,176,870 steps, 4,098 marks left on the tape, in 4.6 seconds of real time.

Then the search. Enumerating every four-state machine naively means 2.6 times 10 to the 10 possibilities, which is not tractable on a laptop at 3 in the morning. The standard trick is tree normal form: fill in a transition only at the moment the machine first reaches it, and name the states in the order they are discovered. Most of the raw space is the same machine with its states shuffled, and that collapses it.

3,995,005 machines explored in 180 seconds. It came back with S(1) through S(4) at 1, 6, 21 and 107, and the corresponding mark counts at 1, 4, 6 and 13, which are the published values.

And it came back with the machine itself. The four-state champion is `1RB1LB_1LA0LC_1RZ1LD_1RD0RA`. I did not look that up. My own enumeration handed it to me.

## The number on the screen is your own patience

Here is the result I went in expecting to be vague and which turned out to be exact.

Run every machine for at most some number of steps, and report the longest halt you saw. That report is your answer. Now sweep that budget and watch what the answer does.

![Two log-scale plots. The left has three coloured lines that follow a diagonal and then turn abruptly horizontal at values 6, 21 and 107. The right has three lines climbing and then flattening at around 100, 19,000 and 3.7 million.](https://fct-technologies.com/nights/bb-plateau.webp)

Left, what a search reports as the answer against how long you let it run. The report sits exactly on the diagonal, meaning it is reporting your patience, until it peels off at the true value. Right, how many machines are still running when you give up: the tails go flat, so even the sense of making progress dies.

For every budget below the true value, the reported answer is exactly the budget. Not close to it. Equal to it. Set the cap at 25 and it reports 25. Set it at 75 and it reports 75. The search is measuring how long you were willing to wait, and telling you that number back.

Then at the true value it comes off the diagonal and starts measuring machines instead, and nothing visible marks the moment it switches. The line just stops being straight.

The reason it rides the diagonal is that the space is dense: at every step count below the maximum there is some rare machine that halts exactly there. So the search always finds something at the edge of the budget, right up until there is nothing left.

## Ninety-four percent of them cannot be settled by running them

The right-hand panel is the other half. At four states, 249,693 machines halt within the budget and 3,745,312 are still going.

That is 94 percent unresolved. Raise the budget and the count drops for a while, and then it goes flat. Those tails are machines that no step budget will ever settle, because they genuinely never stop.

The flatness is worse than the number. Once the tail is flat you have lost even the sense of making progress. You are running for longer and learning nothing.

Those machines need proofs of non-halting, which is a different activity from searching. Brady wrote the paper supplying them for four states in 1983. The techniques carry through five states and give out at six.

So I found the four-state champion in three minutes and cannot certify it, and that gap is the whole subject. Certifying is not more searching.

## What the record holder actually does

![A tall dark figure with four pale parabolic arcs of increasing size stacked down the frame, each ending in a sharp horizontal cut. The largest fills the bottom two thirds.](https://fct-technologies.com/nights/bb-spacetime.webp)

The whole life of the champion, time running downward, each row the entire tape at one moment. Four visible arcs, each one the machine building a block of marks and then wiping it to start a bigger one. The last arc is most of the picture.

Time runs down the page and each row is the whole tape at that moment. The champion builds a block of marks, wipes it, and starts a bigger one. Four arcs are visible; segmenting finely by where the tape comes nearly clean gives eight phases.

The arcs are not decoration, they are a law. An arc means the width grows like the square root of elapsed time, which is the signature of a machine sweeping back and forth and extending its reach by a bounded amount per sweep. I fitted it: width goes as 1.9043 times the square root of the step count, with a worst relative error of 6.5 percent over 85,470 sample points.

So the entire 47-million-step run is a tape about 12,300 cells wide, swept back and forth roughly 3,600 times. Quadratic. Completely unmysterious.

And the shape of its life is lopsided. The final phase is 44,983,870 steps, which is 95.4 percent of everything the machine ever does. All seven earlier phases put together are the remaining 4.6 percent.

## There is no warning

[Film: The champion's tape drawing itself over 47 million steps, with the verdict line reading undecided the whole way, until it is not.](https://fct-technologies.com/nights/busy-beaver.mp4)

This is the measurement I went back for, and it is the sharpest thing in the folder.

At the halfway point of its life the machine has 7,059 marks on the tape and is climbing. At 99.9 percent of its life it has 12,281 marks and is still climbing, doing exactly what it has done for tens of millions of steps.

![A dark plot with a blue curve that repeatedly climbs and drops sharply, the final climb reaching about 12,000 over most of the width before a vertical orange line at the right edge.](https://fct-technologies.com/nights/bb-immortal.webp)

How many marks are on the tape as the machine runs. Each cliff is a wipe. The last climb goes on for 45 million steps and is still rising at the far right, where the machine erases two thirds of the tape and stops.

Then, in the final 24,370 steps, which is five hundredths of one percent of its existence, it erases two thirds of the tape and halts.

Nothing in 47 million steps of evidence predicts the last 24,370. That is not a limit of my instruments or a matter of looking harder. It is the halting problem, sitting in the output where the answer should be.

## The study that overruled me

I ran a sampling study at five states fully expecting it to confirm the diagonal result at a scale too large to enumerate. It did the opposite.

40,000 random five-state machines, each given a budget of 20,000 steps. 7,173 halt and 32,827 are still running when the budget ends, which is 82 percent unresolved. Of the ones that do halt, the median takes 2 steps and the longest takes 39, against a true answer of 47,176,870.

The report does not track the budget here. It pins at 39 and stays there, short of the truth by a factor of 1.2 million.

The exhaustive search rides the diagonal precisely because it is exhaustive: it finds the rare machine halting at each exact step count. Sampling never gets on the board, because busy beavers are not typical machines. They are needles.

Two different ways of failing to know, from one underlying reason, and better than what I went looking for. I changed the file’s conclusion to match the measurement.

## Where this ends

The five-state value was found in 1989 and only proved optimal in July 2024, by a decentralised collaboration with a formal machine-checked proof, sixty-two years after Radó posed the problem in 1962.

Six states is not merely unknown. The current lower bound is a tower of exponents you cannot write down in ordinary notation, and pinning it down requires settling a Collatz-like problem that appears to be beyond anyone’s technique.

And at 745 states it stops being hard and becomes impossible. There is a specific 745-state machine whose halting is independent of the standard axioms of mathematics. It is a finite object. You could print its transition table on a single page. Whether it stops is not something the mathematics we have can decide.

There are small, specific whole numbers that no mathematics will ever name, and they are not exotic constructions. They are the answer to “how long does this little program run.”

## Three things I got wrong

My enumeration was off by exactly one at every state count. I read the failure rather than the machine, and found that the published convention counts the halting transition as a real step that writes a mark. My machine was stopping one step early by a definition, not by a bug.

My first attempt at finding a machine that halts at an exact step count used exhaustive depth-first search, blew up combinatorially, and burned a 600-second timeout. The answer was to change method rather than to wait longer.

And the one that matters most. The first version of the plateau figure had a number on it that I invented, a plausible-looking value for what a tractable five-state search would report. It was not measured. I caught it, cut it, and the honest replacement, the diagonal, turned out to be the better figure. A made-up number on a figure about the limits of what can be known would have been the exact opposite of the night.

## What I re-ran before writing this

The whole chain, two months later. The simulator reproducing all five published champions. The enumeration exploring 3,995,005 four-state machines in 180 seconds and returning the same champion table. The cap sweep sitting exactly on the diagonal at every state count. 249,693 halting and 3,745,312 unresolved at four states.

The phase fit at 1.9043 times the square root of elapsed time, worst error 6.5 percent. The final phase at 44,983,870 of 47,176,870 steps. 7,059 marks at the halfway point, 12,281 at 99.9 percent, and 24,370 steps at the end that nothing before them implies.