Skip to main content
Share Your Experience: Take the 2024 Developer Survey

The Busy Beaver problem is about finding the sequence of n-state Turing Machines writing the most 1's on a tape.

Tibor Radó defined Busy Beavers as Turing Machines that among all halting Turing Machines with the same number of states write the most 1s on the tape, i.e. the $nth$ Busy Beaver writes the most $1$s among all $n$-state Turing Machines.

The Busy Beaver function $\Sigma(n)$ maps $n$ to the number of $1$s written by the $nth$ Busy Beaver. It is proven to be uncomputable as well as growing faster than any computable function.

Radó also defined the Max Shift function $S(n)$ that maps $n$ to the greatest possible number of state shifts made by halting $n$-state Turing Machines which is equivalent to the greatest number of steps. Like $\Sigma(n)$ this function is uncomputable. Since writing a $1$ on the tape requires a shift, $\Sigma(n) \leq S(n)$.

Discussions about the Busy Beaver problem often involve the Max Shift function, since it has similar properties and is easier to reason about.