Beeping Busy Beaver: Difference between revisions
m Not $, but <math> |
m Not $, but <math> |
||
| Line 5: | Line 5: | ||
<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 | where <math>T(n)</math> is the set of Turing machines with <math>n</math> states and two symbols. | ||
== Significance == | == Significance == | ||
Revision as of 12:22, 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.
Formally, we define the th Beeping Busy Beaver number as
where is the set of Turing machines with states and two symbols.
Significance
It is easy to see that , by letting the beep state be the state that is reached immediately before the halt state. Moreover, it turns out that grows uncomputably faster than .
History
Section 5.10 of the seminal survey "The Busy Beaver Frontier" by Scott Aaronson [1] introduced the concept of BBB.