Busy Beaver Lab

3 states · 2 symbols

Steps run, per machine. The tall spikes are the rare ones worth finding.

Outcomes

Halted: 8934
Proved looping: 599
Ran off the tape: 10165
Still running at the cap: 302

1,048,576 machines exist at this state count.

Longest halting machine

21 steps, 6 ones left on the tape.

A0 → 1RB
A1 → 0LH
B0 → 1LB
B1 → 0RC
C0 → 1LC
C1 → 1LA

The machines

States

First machine

The sweep

Machines swept

Step cap

Metrics

Total295 / 500

HALTED45

What is halting share?

Computational experiment

Out of the machines in your window, how many stopped on their own. Neither a high number nor a low one is a win. A window where everything halts is a window full of machines that did almost nothing; a window where nothing halts is one you cannot say much about. The interesting machines are the rare ones that run for a long time and then stop.

Try — Load Hasty and Patient one after the other. Same machines, same window, step cap 20 against 1000 — the halting share moves a long way, and nothing about the machines changed.

Radó (1962) — "On non-computable functions", the paper that defined the busy beaver game

DECIDED48

What is decided share?

Computational experiment

How many machines in your window you actually know the answer for. Two kinds count: the ones that stopped, and the ones caught going round in a circle — once a machine repeats a situation it has been in before, it will repeat it forever, so that is a proof. Everything else is simply unknown. Not "probably never stops" — unknown. Turning that unknown into a certainty for every machine is impossible, and that has been proved.

Try — Raise the step cap and watch this climb while the halting share climbs with it — then notice it stops well short of 100 no matter how high you go. The machines it cannot reach are not stuck; they are unproven.

RECORD100

What is record approach?

Established physics

The longest-running machine you found, compared with the longest one that exists for that number of states. 100 means your search found the champion. The numbers you are chasing are 6 steps for two states, 21 for three and 107 for four — small enough to write down, and it took mathematicians decades to be sure of the last one.

Try — Load Champions. It opens on the window of the three-state enumeration that contains a 21-step machine — read its transition table, then go and try to find another one by moving the window yourself.

ONES100

What is productivity?

Established physics

The most ones any halting machine in your window left written on the tape, compared with the most that is possible. Running the longest and writing the most are different competitions, and they are usually won by different machines — a good reminder that "biggest" depends entirely on what you decided to measure.

Try — Run Complete — the whole two-state enumeration — and compare the two champion tables. Six steps and four ones are won by machines that differ in one transition.

Radó (1962) — "On non-computable functions", the paper that defined the busy beaver game

COVERAGE2

What is coverage?

Established physics

How much of the whole space of machines your window looked at. At two states there are only 1,728 of them, so you can look at every single one — and then your answer is not a good guess, it is a proof. At four states there are more than a billion, and this gauge reads zero however wide you make the window. That gap is what the busy beaver problem is.

Try — Set the states to 2 and widen the window until coverage reads 100. Nothing else on this platform can do that, and the reason is that everything else has infinitely many configurations to try.

Everything not halted and not proved looping is UNDECIDED. That is not a gap in this lab: Turing proved in 1936 that no procedure decides halting for every machine.

Loading lab…

A number nobody can compute, for machines you can read in six lines.

A Turing machine here is a handful of states, a tape of blank cells, and one instruction per (state, symbol) pair: write a bit, move one cell, go to a state or halt. That is the whole rulebook. Tibor Radó asked in 1962 how long the longest-running halting machine with n states runs, and called the answer BB(n). Then he proved it is not computable — because knowing BB(n) would let you decide whether any n-state machine halts, by running it that long and giving up, and Turing had already shown in 1936 that nothing can do that.

The values are absurdly small and absurdly hard. BB(2) = 6 steps. BB(3) = 21. BB(4) = 107, which took until 1983. BB(5) = 47,176,870 was an open question for forty years and was settled in 2024 by a distributed, machine-checked proof. BB(6) is open, and is known to exceed a tower of fifteen tens. This lab stops at four states because that is where the search still fits in a browser — and because stopping there lets you do something no other lab on this platform can.

There are exactly 1,728 two-state machines in this enumeration, and the default sweep runs all of them. That is not a sample: when Coverage reads 100 the search has finished, and the champion it found is BB(2) rather than a guess at it. Every other reading here is a report on a finite search — including Decided, which counts the machines whose fate was proved, either by halting or by repeating a configuration they had already been in. Everything else is unknown, and no larger step cap fixes that in general. That is not a limitation of the lab. It is the theorem.