Beeping Busy Beaver: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
Racheline (talk | contribs)
→Beeping Booping Busy Beavers: mentioned three specific models of BBBB, and included the values for 1-state and 2-state (2-symbol) BBBB
Polygon (talk | contribs)
→BBBB champions: better organisation
 
(31 intermediate revisions by 8 users not shown)
Line 1: Line 1:
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.
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. These can simulate problems in Π₂ and Σ₂ of the [[wikipedia:Arithmetic hierarchy|arithmetic hierarchy]], such as the [[wikipedia:Collatz conjecture|Collatz conjecture]] and [[wikipedia:Twin prime#Twin prime conjecture|twin prime conjecture]].


== Definition ==
== 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
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''. The machine may beep finitely many times (possibly zero) or infinitely many times. 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); set <math>b(M)=0</math> if it never beeps. 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>
Line 8: Line 8:
where <math>T(n)</math> is the set of Turing machines with <math>n</math> 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.
Note that quasihalting does not require halting, so we can consider Turing machines which have no halt transitions. Thus the [[Tree Normal Form]] algorithm needs to be modified (to allow TMs with no halt transitions) when searching for BBB champions.


== Significance ==
Another way to define BBB is to have Turing machines have a special beep transition instead of an entire beep state. Both conventions are denoted BBB here; specify the convention when comparing state counts or last-beep times. For example, Charlie Reams's 18-state twin-prime machine uses the transition from state N reading 0, while [[User:GregoryMorse|GregoryMorse]]'s 19-state machine uses beep state F.<ref>[https://github.com/calr3/tinycryptids/tree/main/twinprimes Reams's twin-prime machine]; [https://github.com/GregoryMorse/NP-complete/blob/main/twin/README.md GregoryMorse's twin-prime machine].</ref>
 
== Growth rate ==


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.
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.
Line 22: Line 24:
etc.
etc.


== Results ==
== Champions ==
This table considers beep states.
{| class="wikitable"
|+
!Domain
!Max Steps
!Champions
!Beep&nbsp;State
!Notes
|-
|BBB(1)
|1
|{{TM|1RZ---|halt}}
|A
|Case analysis by Scott Aaronson.<ref name=":0" />
|-
|BBB(2)
|6
|{{TM|1RB1LB_1LB1LA|non_halt}}
|A
|Case analysis by Scott Aaronson.<ref name=":0" />
|-
|BBB(3)
|55
|{{TM|1RB0LB_1LA0RC_1LC1LA|non_halt}}
|B
|Claimed as a lower bound by Scott Aaronson, verified with exhaustive search by Nick Drozd.<ref name=":0" /><ref>Nick Drozd blog comment, 2021. https://scottaaronson.blog/?p=5661#comment-1900343</ref>
|-
|BBB(4)
|32,779,478
|{{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD|non_halt}}
|D
|Proven in Coq.<ref name=":Coq-BBB4">John Carrino, "[https://github.com/carrino/Coq-BBB4 Coq-BBB4]"</ref>
|-
|BBB(5)
|> 10<sup>14,006</sup>
|{{TM|1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA|non_halt}}
|C
|Best known, per Nick Drozd.<ref>Nick Drozd. https://scottaaronson.blog/?p=8088#comment-1981333</ref> Probably ><math>10^{10^{10^5}}</math> due to four [[probviously]] quasihalting [[Cryptids]].<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/04/03/mother-of-giants.html Mother of Giants].</ref>
|-
|colspan="20" style="text-align:center"|'''3 Symbols'''
|-
|BBB(2,3)
|59
|{{TM|1RB2LB1LA_2LB2RA0RA|non_halt}}
|A
|Per Nick Drozd.<ref>Nick Drozd, "[https://nickdrozd.github.io/2025/03/24/bbb-3-3.html BBB(3,3) > 10↑↑6]". Blog post. Accessed 15 August 2025.</ref>
|-
|BBB(3,3)
|> 10 ↑↑ 10 ↑↑ 10 ↑↑ 3.5
|{{TM|1RB2LB2LA_1LA0RC0LB_2RC2RB0LC|non_halt}}
|all except C
|Best known, per Nick Drozd.<ref>https://discord.com/channels/960643023006490684/1385498968011575366/1571714096502673453</ref>
|-
|colspan="20" style="text-align:center"|'''4 Symbols'''
|-
|BBB(2,4)
|> <math>2 \times 10^{23}</math>
|{{TM|1RB2LA1RA1LB_0LB2RB3RB1LA|non_halt}}
|A
|Best known, per Nick Drozd.<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>
|}


* BBB(1) = 1<ref name=":0" />
All known champions quasihalt by becoming [[Translated Cycler|Translated Cyclers]], a property which is known to be weaker than the general quasihalting condition.
* 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 four "[[probviously]]" quasihalting [[Cryptids]].<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>
==Beeping Booping Busy Beavers==
*BBB(3,3) ≥ 10↑↑6<ref>https://groups.google.com/g/busy-beaver-discuss/c/EuIXSir4Eps</ref> by {{TM|1RB0LB2LA_1LA0RC0LB_2RC2RB0LC}}
A further extension devised by Bram Cohen is as follows: a Turing machine has two special transitions, a beep transition and a boop transition, both of which may repeat infinitely often. The machine "outputs" an integer sequence, indicated by the number of beeps between successive boops. If any such integer is repeated an infinite number of times, the machine is said to '''pseudoquasihalt'''. Now if we define <math>g(M)</math> as the number of transitions for machine M to finish outputting that infinitely-repeated value for the first time (or ∞ if there is no such value), the Beeping Booping Busy Beaver number is:
*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.
<math display="block">\operatorname{BBBB}(n) := \max_{{M \in T(n)\ :\ g(M) < \infty}} g(M)</math>


==Beeping Booping Busy Beavers==
These machines are equivalent to Turing machines with second-order oracles, and so their pseudoquasihalting behavior can describe sets in Π₃ and Σ₃ of the [[wikipedia:Arithmetic hierarchy|arithmetic hierarchy]].<ref>Bram Cohen. 2023. [https://bramcohen.com/p/beeping-booping-busy-beavers Beeping Booping Busy Beavers].</ref>
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>


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.
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.<ref>[https://discord.com/channels/960643023006490684/1243312334907375676/1417836470793670697 Discord message]</ref>
=== BBBB champions ===
 
{| class="wikitable"
|+
!Domain
!Value
!Champions
!Notes
|-
|BBBB(1)
|2
|{{TM|0RA---|non_halt}} (beep: any, boop: A0)
|Confirmed.<ref>racheline, September 2025. [https://discord.com/channels/960643023006490684/1243312334907375676/1417839422191308871 Discord message]</ref>
|-
|BBBB(2)
|18
|{{TM|0RB1LB_1LA1RB|non_halt}} (beep: A0, boop: A1)
|Proved.<ref name=":1">Crorem, Gitlab https://gitlab.com/Crorem/coq-bbbb3</ref>
|-
|BBBB(3)
|127
|{{TM|1RB1LB_0RC0LA_1LC0LA|non_halt}} (beep: B0, boop: B1)
|Proved
|-
|colspan="20" style="text-align:center"|'''3 Symbols'''
|-
|BBBB(2,3)
|177
|{{TM|1RB0LB2LB_2LA2RB1LB|non_halt}} (beep: A0, boop: A2)
|Proved.<ref name=":1" />
|}
 
==Higher-order Beavers==
For higher order functions, using https://katelyndoucette.com/articles/building-the-busy-beaver-ladder definition, we can get BBBBB(1) = 2 and BBBBB(2) ≥ 18.


== References ==
== References ==


[[category:Functions]]
[[category:Functions]]

Latest revision as of 19:36, 17 November 2026

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. These can simulate problems in Π₂ and Σ₂ of the arithmetic hierarchy, such as the Collatz conjecture and twin prime conjecture.

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. The machine may beep finitely many times (possibly zero) or infinitely many times. 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 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)=∞ if the TM never stops beeping); set b(M)=0 if it never beeps. Then

BBB⁡(n):=maxM∈T(n) : b(M)<∞b(M)

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

Note that quasihalting does not require halting, so we can consider Turing machines which have no halt transitions. Thus the Tree Normal Form algorithm needs to be modified (to allow TMs with no halt transitions) when searching for BBB champions.

Another way to define BBB is to have Turing machines have a special beep transition instead of an entire beep state. Both conventions are denoted BBB here; specify the convention when comparing state counts or last-beep times. For example, Charlie Reams's 18-state twin-prime machine uses the transition from state N reading 0, while GregoryMorse's 19-state machine uses beep state F.[3]

Growth rate

It is easy to see that BBB⁡(n)≥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)>BBn(n), where BBk represents k iterations of BB
  • BBB(n)>BBBB(n)(n)

etc.

Champions

This table considers beep states.

Domain Max Steps Champions Beep State Notes
BBB(1) 1 1RZ--- (bbch) A Case analysis by Scott Aaronson.[1]
BBB(2) 6 1RB1LB_1LB1LA (bbch) A Case analysis by Scott Aaronson.[1]
BBB(3) 55 1RB0LB_1LA0RC_1LC1LA (bbch) B Claimed as a lower bound by Scott Aaronson, verified with exhaustive search by Nick Drozd.[1][4]
BBB(4) 32,779,478 1RB1LD_1RC1RB_1LC1LA_0RC0RD (bbch) D Proven in Coq.[5]
BBB(5) > 1014,006 1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA (bbch) C Best known, per Nick Drozd.[6] Probably >1010105 due to four probviously quasihalting Cryptids.[7]
3 Symbols
BBB(2,3) 59 1RB2LB1LA_2LB2RA0RA (bbch) A Per Nick Drozd.[8]
BBB(3,3) > 10 ↑↑ 10 ↑↑ 10 ↑↑ 3.5 1RB2LB2LA_1LA0RC0LB_2RC2RB0LC (bbch) all except C Best known, per Nick Drozd.[9]
4 Symbols
BBB(2,4) > 2×1023 1RB2LA1RA1LB_0LB2RB3RB1LA (bbch) A Best known, per Nick Drozd.[10]

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

A further extension devised by Bram Cohen is as follows: a Turing machine has two special transitions, a beep transition and a boop transition, both of which may repeat infinitely often. The machine "outputs" an integer sequence, indicated by the number of beeps between successive boops. If any such integer is repeated an infinite number of times, the machine is said to pseudoquasihalt. Now if we define g(M) as the number of transitions for machine M to finish outputting that infinitely-repeated value for the first time (or ∞ if there is no such value), the Beeping Booping Busy Beaver number is:

BBBB⁡(n):=maxM∈T(n) : g(M)<∞g(M)

These machines are equivalent to Turing machines with second-order oracles, and so their pseudoquasihalting behavior can describe sets in Π₃ and Σ₃ of the arithmetic hierarchy.[11]

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.

BBBB champions

Domain Value Champions Notes
BBBB(1) 2 0RA--- (bbch) (beep: any, boop: A0) Confirmed.[12]
BBBB(2) 18 0RB1LB_1LA1RB (bbch) (beep: A0, boop: A1) Proved.[13]
BBBB(3) 127 1RB1LB_0RC0LA_1LC0LA (bbch) (beep: B0, boop: B1) Proved
3 Symbols
BBBB(2,3) 177 1RB0LB2LB_2LA2RB1LB (bbch) (beep: A0, boop: A2) Proved.[13]

Higher-order Beavers

For higher order functions, using https://katelyndoucette.com/articles/building-the-busy-beaver-ladder definition, we can get BBBBB(1) = 2 and BBBBB(2) ≥ 18.

References