Busy Beaver Explained: BB(5) Solved, BB(6) Still Open

Quick answer: The busy beaver number BB(n) is the greatest number of steps a halting two-symbol Turing machine with n working states can take, starting from an all-zero tape (the separate halt state is not counted). BB(5) = 47,176,870, a result announced by the bbchallenge collaboration in July 2024 with a proof checked in Coq, now called Rocq. The exact value of BB(6) is unknown.

Imagine the simplest possible computer: a tape of 0s and a head that follows a few rules. Some rule sets run forever. Others stop. The busy beaver question asks: among all machines with \(n\) working states that eventually stop, which one runs the longest? Running forever disqualifies a machine. Finding a long-running contender is only half the challenge; proving it is the winner means showing that no other eligible machine runs longer. For five states, that took 62 years after Tibor Radó posed the problem, and an international team of volunteers.

What Is a Turing Machine?

A Turing machine has an infinite tape of cells, each holding 0 or 1, a head that reads one cell at a time, and a small set of states. Each rule says: in this state, reading this symbol, write a symbol, move left or right, and switch to a new state (or halt). Despite their simplicity, Turing machines can carry out any computation a modern computer can.

What Is the Busy Beaver Function?

Tibor Radó defined it in 1962. Start each two-symbol machine with \(n\) working states on a blank tape. Among the machines that eventually halt, \(BB(n)\) (also written \(S(n)\)) is the largest number of steps taken. A separate function, \(\Sigma(n)\), is the most 1s left on the tape. They are different optimization problems: at three states, the machine with the most steps is not the one that leaves the most 1s.

States \(n\)Exact steps \(BB(n)\)Max final 1s \(\Sigma(n)\)Status
1111962
2641962
32161963 (published 1965)
4107131983
547,176,8704,0982024
6Unknown (see below)UnknownOpen

A Two-State Example: Six Steps, Four 1s

Start in state A on an all-zero tape:

StateReading 0Reading 1
AWrite 1, move right, go to BWrite 1, move left, go to B
BWrite 1, move left, go to AWrite 1, move right, halt

Label the starting cell 0. On its six steps the head reads cells 0, 1, 0, −1, −2, −1, then halts, leaving four 1s. This shows \(BB(2) \ge 6\) and \(\Sigma(2) \ge 4\); proving these are exact also requires checking every other two-state machine.

Why Is It So Hard?

You might think you could just run every machine and see. The problem is the machines that never halt: you cannot tell them apart from machines that will halt after a very long time just by waiting. This is Alan Turing’s halting problem. No single algorithm can decide it for every machine, and for the same reason no algorithm can compute \(BB(n)\) for every \(n\); it grows faster than any computable function. Particular values can still be found with computation plus proof.

One useful trick: if a machine ever repeats its entire configuration (state, head position and tape), it is deterministic, so it will repeat forever. Repeating just the state is not enough.

How BB(5) Was Proved

Part of the argumentWhat it establishes
Exhibit a machine that halts after 47,176,870 steps\(BB(5) \ge 47{,}176{,}870\)
Prove every eligible machine either halts by then or never halts\(BB(5) \le 47{,}176{,}870\)
Combine the two\(BB(5) = 47{,}176{,}870\)

The formal proof enumerated 181,385,789 machines after reductions and showed that each one either halts within the bound or runs forever.

  • The champion. In 1989, Heiner Marxen and Jürgen Buntrock found a 5-state machine that halts after exactly 47,176,870 steps. For 35 years nobody could prove there wasn’t a longer one.
  • The collaboration. In 2022, Tristan Stérin launched the Busy Beaver Challenge (bbchallenge), an open online project. Volunteers, many without academic positions, wrote “deciders”: programs that prove whole families of machines run forever.
  • The hardest cases. A handful of machines resisted, including one known as Skelet #17, and needed custom proofs.
  • The verification. On July 2, 2024, the team announced that every case was settled, with the whole argument checked in the Coq (now Rocq) proof assistant, led by a contributor known as mxdys. A human-readable paper was posted in September 2025 and published in the STOC 2026 proceedings.

Why BB(6) Is Different

The exact value of \(BB(6)\) is unknown. In June 2025, mxdys found a six-state machine proved to halt after more than \(2 \uparrow\uparrow\uparrow 5\) steps, which gives a lower bound. The arrows describe repeated operations: \(2 \uparrow\uparrow 4 = 2^{2^{2^2}} = 65{,}536\) (see our guide to exponent rules), and triple arrows repeat that tower-building again. The project’s records give an even stronger bound.

The difficulty also comes from unresolved machines. Antihydra, a six-state machine, encodes a Collatz-like iteration whose long-term behavior nobody has proved; it is related to, but not the same as, the Collatz conjecture. As of October 30, 2026, the project listed 608 six-state holdouts (counting equivalent machines once).

Uncomputable does not mean infinite. Every busy beaver value is a finite whole number, because there are finitely many machines and only halting ones count. Separately, logicians have shown that under standard consistency assumptions, some busy beaver values for machines with a few hundred states cannot be established within ZFC, the usual foundation of mathematics. That has not been shown for \(BB(6)\).

Common Misconceptions

“BB(5) was found by brute force.” Running machines was not enough; the hard part was proving that non-halting machines never halt.

“Computers can calculate BB(n) given enough time.” No algorithm computes \(BB(n)\) for every \(n\). Individual values can still be settled, as \(BB(5)\) was, by combining computation with proof.

Watch: The Busy Beaver in Video

If you learn better by watching, these videos are worth your time.

BB(5) = 47,176,870 (Polylog). A detailed visual explanation of the problem and the proof.
Busy Beaver: The Hardest Game in Computer Science (Quanta Magazine). Quanta’s explainer on the BB(5) collaboration.
Skelet #17: The Last Obstacle to solving Busy Beaver 5 (NLogSpace). Advanced, optional: how one stubborn machine was finally proved to run forever.

Check Your Understanding

Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.

Answer each question and press Submit to see your result right away.

1. What does BB(n) measure?
Found a bug? Let us know!
2. Does the halt state count toward n in BB(n)?
Found a bug? Let us know!
3. Why can’t you find BB(n) by running every machine?
Found a bug? Let us know!
4. Finding one machine that halts after many steps proves what about BB(n)?
Found a bug? Let us know!
5. Why is BB(6) expected to be so hard?
Found a bug? Let us know!

Frequently Asked Questions

What is the busy beaver number?

For each n, the busy beaver number BB(n) is the largest number of steps taken by an n-state, two-symbol Turing machine that eventually halts when started on a blank tape. Tibor Radó introduced it in 1962.

What is BB(5)?

BB(5) = 47,176,870. The bbchallenge collaboration announced a Coq-verified proof on July 2, 2024.

Is BB(6) known?

No. In 2025 a six-state machine was proved to halt after more than 2↑↑↑5 steps, a lower bound. As of October 2026, 608 six-state machines remained unresolved, some tied to Collatz-like open problems.

Is BB(6) infinite?

No. Only halting machines count and there are finitely many six-state machines, so BB(6) is a finite number. It is just unknown and enormous.

Are BB(n) and Σ(n) the same?

No. BB(n), also written S(n), counts the most steps; Σ(n) counts the most 1s left on the tape. For example, BB(5) = 47,176,870 while Σ(5) = 4,098.

Why is the busy beaver function uncomputable?

If a program could compute BB(n) for every n, it could solve the halting problem by running each machine for BB(n) steps. Turing proved the halting problem is unsolvable, so no such program exists. Individual values can still be determined by proof.

Keep Exploring

Sources and Further Reading

Related to This Article

What people say about "Busy Beaver Explained: BB(5) Solved, BB(6) Still Open - Effortless Math"?

No one replied yet.

Leave a Reply