The Busy Beaver problem, introduced by Tibor Radó in 1962, asks how much a halting Turing machine with a given number of states can do before it stops. It is one of the cleanest ways to see where computation ends.

🦫 What is the Busy Beaver problem?

Take every Turing machine with n states and two symbols, start each one on a blank tape, and keep only those that eventually halt. Two functions measure the winners. The score Σ(n) is the largest number of 1s any of them leaves on the tape, and S(n) is the largest number of steps any of them takes before halting. A machine that reaches the maximum is called a busy beaver for that number of states.

🚀 Why is it significant

Both functions grow faster than any computable function. If S(n) were computable, you could decide the halting problem: run a machine with n states for S(n) steps, and if it has not halted by then, it never will. Since the halting problem is undecidable, no algorithm can compute S(n) for every n.

🔍 Known values

nΣ(n)S(n)
111
246
3621
413107
5409847,176,870

The value for five states was open for decades. In 2024 the bbchallenge collaboration settled it with a proof checked in Coq, confirming the machine Heiner Marxen and Jürgen Buntrock found in 1989. For six states only lower bounds are known, and they are already far too large to write out in decimal.

🛠️ Implications for computability

The problem turns undecidability into a number. For each n, Σ(n) and S(n) are well-defined integers, yet no single algorithm produces all of them. From 745 states up, the exact value cannot be proved within ZFC, the usual axioms of mathematics (assuming ZFC is consistent).

📚 Further reading