Busy Beaver

Name the biggest number

Here's a game you might have played as a kid: who can name the biggest number? Now give it rules. Your number has to be printed by a program at most 100 characters long, and the program has to finish.

There are only finitely many programs that short. Most don't run. Some run forever. Of the ones that finish and print a number, one prints the biggest. That number is, more or less, the busy beaver of 100. It's perfectly well defined. You just can't compute it.

A Turing machine

Instead of Python we use the simplest programming language there is. Memory is a tape of cells, each 0 or 1, all 0 at the start. A head sits on one cell. The program is a few states, and each state has two rules: one for when the head reads 0, one for when it reads 1. A rule says what to write, which way to move, and which state to go to next. One rule can lead to HALT, and if the machine ever takes it, it stops.

states

colored circles. The head's outline takes the current state's color.

rules

arrows labelled with the move. An open tail fires on a 0, a filled tail on a 1.

tape

white is 0, dark is 1. It's infinite both ways.

history

the tape at every moment, oldest at the top, now at the bottom. Each 1 is painted in the color of the state that wrote it.

The name 1RB1LB_1LA1RZ is the whole program: one group per state, read-0 rule then read-1 rule. 1RB means write 1, move right, go to B. Z is HALT.

The busy beaver of n

Take every Turing machine with n states and run each one on a blank tape. Some run forever. Of the ones that halt, find the one that runs longest. Its number of steps is BB(n).

With two states there are 12 choices for each of the four rules, so 20,736 machines. Here are all of them, one square each, sorted by how they ended. Grey ones were still running after 100 steps. Green ones halted, darker the longer they ran. The pink ones at the very end ran longest:

The catch: to prove BB(2) = 6, it isn't enough to find a machine that runs 6 steps. You have to show that every machine still running after 6 steps never stops. Above, we gave up on them after 100 steps, which proves nothing. For two states the proof is a homework problem. It gets much harder.

The champions

Each card is the longest-running halting machine of its size, drawn as its history. Tap one to open it in the playground.

BB(1) is 1: a single state can only stop right away or walk off forever. BB(3) = 21 was a PhD thesis in 1963. BB(4) = 107 took Allen Brady until 1983, sorting through billions of machines with whatever computers he could get.

BB(5) = 47,176,870

In 1989 Heiner Marxen and Jürgen Buntrock found a five-state machine that halts after 47,176,870 steps. For 35 years nobody could prove that no other five-state machine runs longer. In 2024 the bbchallenge collaboration, mostly volunteers on a Discord server, finally did it, with a proof checked by computer.

Run all 47 million steps

What is it doing all that time? It's computing a Collatz-like sequence. Start at n = 0 and look at the remainder when n is divided by 3. Remainder 0 or 1 gives the next n; remainder 2 halts.

Each step of the sequence takes the machine time proportional to n², which is why the history fills up with ever-wider sweeps.

A field guide

The machines that never halt are the hard part, and they have a zoo of behaviours. Researchers gave them names the way biologists name species. All of these run forever.

Skelet #1 was among the last five-state machines anyone could settle. It acts like a counter in base 4, mixed with chaos, and after layer on layer of acceleration researchers showed that, roughly 10⁵¹ steps in, it settles into a loop and never halts.

BB(6): here be cryptids

Six states is where it breaks. The best-known halting machine runs for a number of steps that is a tower of twos, whose height is a tower of twos, whose height is a tower of twos. We only know it halts because, like the BB(5) champion, it repeats a math function until a condition is met, and that can be worked out without running it.

Worse, some six-state machines are cryptids: deciding if they halt means solving open problems in mathematics. Antihydra halts only if a Collatz-style process ever drifts one particular way, and nobody can prove that it will or that it won't.

Why nobody can compute BB

If you knew BB(10), you could decide whether any ten-state machine halts: run it for BB(10) steps. If it hasn't halted by then, it never will. That works for every n. But Turing proved that no program can decide halting for every machine, so no program can compute BB(n) for every n.

It gets stranger. A Turing machine with about 25 states halts if and only if the Goldbach conjecture is false. And for machines with a few hundred states, the value of BB doesn't follow from the standard axioms of mathematics at all. Even the axioms can't say whether some of those machines halt.

So busy beaver is a function everyone can define and nobody can compute. Pinning down its values is less like writing programs and more like biology: going out, finding what's living in the space of tiny machines, and naming it.

Playground

Edit the transition table, or paste a machine in the standard format. The link in your address bar always holds the current machine, so you can share it.