Beeping Busy Beaver

The Beeping Busy Beaver (BBB) function is a variant of the Busy Beaver function proposed by Scott Aaronson in his 2020 Busy Beaver Frontier survey. It is notable because it is uncomputable even if you have access to a halting oracle for Turing Machines.

Definition

Consider a beeping Turing machine, which is a Turing machine that has a special state named "beep state". Every time the TM enters the "beep state" it beeps. There are two possibilities, either this TM beeps a finite number of times (and thus there is a final beep) or it never stops beeping. Nick Drozd coined the term quasihalting to describe the event when a TM last beeps. A TM quasihalts if it beeps only a finite number of times. The Beeping Busy Beaver problem is analogous to the Busy Beaver problem, replacing halting with quasihalting. In other words, let $b(M)$ be the number of steps the machine M takes until it quasihalts (beeps for the last time) if it quasihalts (we will say $b(M)=\infty$ if the TM never stops beeping). Then

$$\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.

Note that these Turing machines need not ever halt, so the Tree Normal Form algorithm needs to be modified (to allow TMs with no halt transitions) when searching for BBB champions.

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}$ (as fast as BB augmented with a halting oracle).

Results

• BBB(1) = 1
• BBB(2) = 6
• BBB(3) = 55
• BBB(4) ≥ 32,779,478
• BBB(5) ≥ 10^14,006 and probably $BBB(5)\geq 10^{10^{10^{5}}}$ due to a "probviously" halting Cryptid.

All known champions quasihalt by becoming Translated Cyclers, a property which is known to be weaker than the general quasihalting condition.