Beeping Busy Beaver: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
(Created page with "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$<sup>th</sup> Beeping Busy Beaver number as <math display="block">\operatorname{BBB}(...")
 
(→‎Results: Changed score of BBB(2,4) champion, the old one might have been a typo)
 
(24 intermediate revisions by 7 users not shown)
Line 1: Line 1:
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.
The '''Beeping Busy Beaver''' (BBB) function is a variant of the [[Busy Beaver Functions|Busy Beaver function]] proposed by Scott Aaronson in his 2020 [[Busy Beaver Frontier]] survey.<ref name=":0">Scott Aaronson. "The Busy Beaver Frontier". https://www.scottaaronson.com/papers/bb.pdf</ref> It is notable because it is uncomputable even if you have access to a halting oracle for Turing Machines.


Formally, we define the $n$<sup>th</sup> Beeping Busy Beaver number as
== 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 [[Quasihalt|quasihalting]] to describe the event when a TM last beeps. A TM quasihalts if it beeps only a finite number of times.<ref>Nick Drozd. 2020. [https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.html Beeping Busy Beavers].</ref> The Beeping Busy Beaver problem is analogous to the Busy Beaver problem, replacing halting with quasihalting. In other words, let <math>b(M)</math> be the number of steps the machine M takes until it quasihalts (beeps for the last time) if it quasihalts (we will say <math>b(M) = \infty</math> if the TM never stops beeping). Then


<math display="block">\operatorname{BBB}(n) := \max_{{M \in T(n)\ :\ b(M) < \infty}} b(M)</math>
<math display="block">\operatorname{BBB}(n) := \max_{{M \in T(n)\ :\ b(M) < \infty}} b(M)</math>


where $T(n)$ is the set of Turing machines with $n$ states and two symbols.
where <math>T(n)</math> is the set of Turing machines with <math>n</math> 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 ==
== Significance ==


It is easy to see that $\operatorname{BBB}(n) \ge \operatorname{BB}(n)$, by letting the beep state be the state that is reached immediately before the halt state. Moreover, it turns out that $\operatorname{BBB}$ grows uncomputably faster than $\operatorname{BB}$.
It is easy to see that <math>\operatorname{BBB}(n) \ge \operatorname{BB}(n)</math>, by letting the beep state be the state that is reached immediately before the halt state.


== History ==
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:
Section 5.10 of the seminal survey "The Busy Beaver Frontier" by Scott Aaronson <ref name=":0">https://www.scottaaronson.com/papers/bb.pdf</ref> introduced the concept of BBB.
 
* <math>BBB(n) > BB(BB(n))</math>
* <math>BBB(n) > BB^n(n)</math>, where <math>BB^k</math> represents k iterations of BB
* <math>BBB(n) > BB^{BB(n)}(n)</math>
 
etc.
 
== Results ==
 
* BBB(1) = 1<ref name=":0" />
* BBB(2) = 6<ref name=":0" /> by {{TM|1RB1LB_1LB1LA}}
* BBB(3) = 55 by {{TM|1LB0RB_1RA0LC_1RC1RA}}
* BBB(4) ≥ 32,779,478 by {{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD}}
* BBB(5) ≥ 10<sup>14,006</sup><ref>Nick Drozd. https://scottaaronson.blog/?p=8088#comment-1981333</ref> by {{TM|1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA}} and probably <math>BBB(5) \ge 10^{10^{10^5}}</math> due to a "[[probviously]]" quasihalting [[Cryptids|Cryptid]].<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/04/03/mother-of-giants.html Mother of Giants].</ref>
 
*BBB(2,3) = 59<ref>Nick Drozd. "[https://nickdrozd.github.io/2025/03/24/bbb-3-3.html BBB(3,3) > 10↑↑6]". Accessed 15 August 2025.</ref>
*BBB(3,3) ≥ 10↑↑6<ref>https://groups.google.com/g/busy-beaver-discuss/c/EuIXSir4Eps</ref> by {{TM|1RB0LB2LA_1LA0RC0LB_2RC2RB0LC}}
*BBB(2,4) > <math>2 \times 10^{23}</math><ref>Nick Drozd. "[https://nickdrozd.github.io/2022/02/11/latest-beeping-busy-beaver-results.html Latest Beeping Busy Beaver Results]". Accessed 15 August 2025.</ref> by {{TM|1RB2LA1RA1LB_0LB2RB3RB1LA}}
 
All known champions quasihalt by becoming [[Translated Cycler|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.<ref>Bram Cohen. 2023. [https://bramcohen.com/p/beeping-booping-busy-beavers Beeping Booping Busy Beavers].</ref>


== References ==
== References ==
[[category:Functions]]

Latest revision as of 17:03, 15 August 2025

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.[1] 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.[2] The Beeping Busy Beaver problem is analogous to the Busy Beaver problem, replacing halting with quasihalting. In other words, let be the number of steps the machine M takes until it quasihalts (beeps for the last time) if it quasihalts (we will say if the TM never stops beeping). Then

where is the set of Turing machines with 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 , 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:

  • , where represents k iterations of BB

etc.

Results

  • BBB(2,3) = 59[5]
  • BBB(3,3) ≥ 10↑↑6[6] by 1RB0LB2LA_1LA0RC0LB_2RC2RB0LC (bbch)
  • BBB(2,4) > [7] 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.[8]

References

  1. ↑ 1.0 1.1 1.2 Scott Aaronson. "The Busy Beaver Frontier". https://www.scottaaronson.com/papers/bb.pdf
  2. ↑ Nick Drozd. 2020. Beeping Busy Beavers.
  3. ↑ Nick Drozd. https://scottaaronson.blog/?p=8088#comment-1981333
  4. ↑ Shawn Ligocki. 2022. Mother of Giants.
  5. ↑ Nick Drozd. "BBB(3,3) > 10↑↑6". Accessed 15 August 2025.
  6. ↑ https://groups.google.com/g/busy-beaver-discuss/c/EuIXSir4Eps
  7. ↑ Nick Drozd. "Latest Beeping Busy Beaver Results". Accessed 15 August 2025.
  8. ↑ Bram Cohen. 2023. Beeping Booping Busy Beavers.
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Beeping_Busy_Beaver&oldid=3176"