The busy beaver: the longest a small machine can run (Radó 1962)

Radó asked: among all Turing machines with n states that halt when started on a blank tape, which runs longest? Call that number of steps S(n). For n = 2, a search over every machine gives S(2) = 6. But S grows faster than any computable function: S(3) = 21, S(4) = 107, and S(5) = 47,176,870, proved only in 2024. Knowing S(n) would solve the halting problem for n-state machines, so no algorithm computes it.

What to look for

The exhaustive search finds the 2-state champion, which halts after 6 steps with 4 ones on the tape. Its step count is reached long before the search’s budget, but proving that the remaining “unknown” machines never halt is exactly what the search cannot do.

The history behind this experiment: Breakthroughs in Replicated Execution. See Exercises: execution for a worked solution to the exercise.

Search all 20,736 two-state machines

import matplotlib.pyplot as plt
import numpy as np

import blockchainkit as bk

result = bk.vm.busy_beaver(2, max_steps=50)
print(result.steps, "steps,", result.ones, "ones:", result.machine)
print(result.counts)
assert (result.steps, result.ones) == (6, 4)

6 steps, 4 ones: {('A', 0): (1, -1, 'B'), ('A', 1): (1, 1, 'B'), ('B', 0): (1, 1, 'A'), ('B', 1): (1, -1, 'H')}
{'halted': 9784, 'looping': 430, 'unknown': 10522}

How long halting machines run

lengths = [
    run.steps
    for run in (
        bk.vm.run_turing_machine(rules, max_steps=50) for rules in bk.vm.enumerate_machines(2)
    )
    if run.outcome == "halted"
]
assert max(lengths) == 6

fig, (left, right) = plt.subplots(1, 2, figsize=(10, 4))
left.hist(lengths, bins=np.arange(0.5, 7.5), color="#7c3aed", edgecolor="white")
left.set(xlabel="steps to halt", ylabel="machines", title="Halting 2-state machines")
known = {1: 1, 2: 6, 3: 21, 4: 107, 5: 47_176_870}
right.semilogy(list(known), list(known.values()), "o-")
right.set(xlabel="states n", ylabel="S(n)", title="Busy beaver values (known)")
fig.tight_layout()

Exercise

bk.vm.run_turing_machine reproduces the 3-state champion’s 21 steps from its rule table (see the history page). Why does a gas limit of 22 steps let you run it but not know that no other 3-state machine runs longer?