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.

Growth rate

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.

In fact, BBB grows much faster than BB. BBB eventually dominates any computable function augmented with an oracle for computing BB. So, for example, there exists some N such that for all n > N:

• $BBB(n)>BB(BB(n))$
• $BBB(n)>BB^{n}(n)$, where $BB^{k}$ represents k iterations of BB
• $BBB(n)>BB^{BB(n)}(n)$

etc.

Results

• BBB(1) = 1
• BBB(2) = 6 by 1RB1LB_1LB1LA (bbch)
• BBB(3) = 55 by 1RB0LB_1LA0RC_1LC1LA (bbch)
• BBB(4) ≥ 32,779,478 by 1RB1LD_1RC1RB_1LC1LA_0RC0RD (bbch)
• BBB(5) ≥ 10^14,006 by 1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA (bbch) and probably $BBB(5)\geq 10^{10^{10^{5}}}$ due to four "probviously" quasihalting Cryptids.

• BBB(2,3) = 59 by 1RB2LB1LA_2LB2RA0RA (bbch)
• BBB(3,3) ≥ 10↑↑6 by 1RB0LB2LA_1LA0RC0LB_2RC2RB0LC (bbch)
• BBB(2,4) > $2\times 10^{23}$ by 1RB2LA1RA1LB_0LB2RB3RB1LA (bbch)

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

Beeping Booping Busy Beavers

An extension devised by Bram Cohen goes as follows: a Turing machine has two special transitions, a beep transition and a boop transition, both of which repeat infinitely often. The machine outputs an integer sequence corresponding to the number of beeps between successive boops. The machine's number is the number of transitions it takes to finish the first output value that is repeated infinitely many times. These machines are considered equivalent to Turing machines with second-order oracles.

There are multiple models to choose from, depending on whether one allows multiple beep transitions and multiple boop transitions, or only one of each, or only one boop transition while making every transition a beep transition. All of these models have the same computational strength and corresponding growth rate, but each has its own advantages. The first is the most general, including all machines from the other two, and in that sense it is more natural, but that makes the space of candidate machines to search through significantly larger. The second is the original definition and it is relatively simple. The third is equivalent to simply considering the amount of time between successive boops, instead of the number of beeps between successive boops, and has the smallest space of candidate machines. It is not yet decided which of these models (or perhaps a model different from all three) should be chosen for "the" BBBB function.

It is known that for all three of these models, BBBB(1) = 2 and BBBB(2) = 17.