Beeping Busy Beaver

A Beeping Busy Beaver (BBB) is a concept defined on a beeping Turing machine, which is a Turing machine that has a special state named "beep state". The goal of a BBB is as follows: when starting from a totally blank tape, we want the final beep to happen as late as possible. The phrasing "final beep" means that the machine must beep finitely many times.

Formally, we define the $n$^th Beeping Busy Beaver number as

$$\operatorname {BBB} (n):=\max _{M\in T(n)\ :\ b(M)<\infty }b(M)$$

where $T(n)$ is the set of Turing machines with $n$ states and two symbols.

Significance

It is easy to see that $\operatorname {BBB} (n)\geq \operatorname {BB} (n)$, by letting the beep state be the state that is reached immediately before the halt state.

Values $>\operatorname {BB} (n)$ may occur when the machine emits a beep before entering non-halting behavior.

Moreover, it turns out that $\operatorname {BBB}$ grows uncomputably faster than $\operatorname {BB}$.

History

Section 5.10 of the seminal survey "The Busy Beaver Frontier" by Scott Aaronson introduced the concept of BBB.