Beeping Busy Beaver: Difference between revisions
m (Add sentence that clarifies difference between BB(n) and BBB(n)) |
(Add some details) |
||
| 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. | 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. It was coined by Scott Aaronson in his 2020 "The Busy Beaver Frontier" survey.<ref>Scott Aaronson. "The Busy Beaver Frontier". https://www.scottaaronson.com/papers/bb.pdf</ref> | ||
Formally, we define the <math>n</math><sup>th</sup> Beeping Busy Beaver number as | Formally, we define the <math>n</math><sup>th</sup> Beeping Busy Beaver number as | ||
| Line 6: | Line 6: | ||
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. | |||
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. | |||
== Significance == | == Significance == | ||
| Line 13: | Line 17: | ||
Values <math>> \operatorname{BB}(n)</math> may occur when the machine emits a beep before entering non-halting behavior. | Values <math>> \operatorname{BB}(n)</math> may occur when the machine emits a beep before entering non-halting behavior. | ||
Moreover, it turns out that <math>\operatorname{BBB}</math> grows uncomputably faster than <math>\operatorname{BB}</math>. | Moreover, it turns out that <math>\operatorname{BBB}</math> grows uncomputably faster than <math>\operatorname{BB}</math> (as fast as BB augmented with a halting oracle). | ||
== Results == | |||
* BBB(3) = 55 | |||
* BBB(4) ≥ 32,779,478 | |||
* BBB(5) ≥ 10<sup>14,006</sup><ref>Nick Drozd. https://scottaaronson.blog/?p=8088#comment-1981333</ref> and probably <math>BBB(5) \ge 10^{10^{10^5}}</math> due to a "[[probviously]]" halting [[Cryptids|Cryptid]].<ref>Shawn Ligocki. Mother of Giants.https://www.sligocki.com/2022/04/03/mother-of-giants.html</ref> | |||
All known champions quasihalt by becoming [[Translated Cycler|Translated Cyclers]], a property which is known to be weaker than the general quasihalting condition. | |||
== References == | == References == | ||
Revision as of 19:20, 10 July 2024
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. It was coined by Scott Aaronson in his 2020 "The Busy Beaver Frontier" survey.[1]
Formally, we define the th Beeping Busy Beaver number as
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.
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.
Significance
It is easy to see that , by letting the beep state be the state that is reached immediately before the halt state.
Values may occur when the machine emits a beep before entering non-halting behavior.
Moreover, it turns out that grows uncomputably faster than (as fast as BB augmented with a halting oracle).
Results
- BBB(3) = 55
- BBB(4) ≥ 32,779,478
- BBB(5) ≥ 1014,006[2] and probably due to a "probviously" halting Cryptid.[3]
All known champions quasihalt by becoming Translated Cyclers, a property which is known to be weaker than the general quasihalting condition.
References
- ↑ Scott Aaronson. "The Busy Beaver Frontier". https://www.scottaaronson.com/papers/bb.pdf
- ↑ Nick Drozd. https://scottaaronson.blog/?p=8088#comment-1981333
- ↑ Shawn Ligocki. Mother of Giants.https://www.sligocki.com/2022/04/03/mother-of-giants.html