= Busy beaver
{tag=Function problem}
{wiki}
= Busy beaver game
{synonym}
The busy beaver game consists in finding, for a given $n$, the turing machine with $n$ states that writes the largest possible number of 1's on a tape initially filled with 0's. In other words, computing the <busy beaver function> for a given $n$.
There are only finitely many Turing machines with $n$ states, so we are certain that there exists such a maxium. Computing the <Busy beaver function> for a given $n$ then comes down to solving the halting problem for every single machine with $n$ states.
Some variant definitions define it as the number of time steps taken by the machine instead. Wikipedia talks about their relationship, but no patience right now.
The Busy Beaver problem is cool because it puts the <halting problem> in a more precise numerical light, e.g.:
* the <Busy beaver function> is the most obvious <uncomputable function> one can come up with starting from the <halting problem>
* the <Busy beaver scale> allows us to gauge the difficulty of proving certain (yet unproven!) mathematical <conjectures>
Bibliography:
* https://www.scottaaronson.com/blog/?p=4916
* https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210
Back to article page