View source for User:Qwerpiw/List of BB functions

* Maximum space: Ben-Amram call this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. This is the total number of tape cells read before halting. According to Ben-Amram, it includes the starting cell, but not necessarily the cell the halting transition moves to.<ref name=":0" />
* [[Maximum Consecutive Ones Function|Maximum consecutive ones]]: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.
* <math>N_e</math> function: Radó formulated the number of halting machines in terms of the set of all valid busy beaver entries <math>M,s</math> where <math>M</math> is the Turing machine, and <math>s</math> is the exact number of steps the halting Turing machine took. The set of all halting <math>n</math>-card machines is denoted <math>E_n</math>, and the cardinality of this set is denoted <math>N_e(n)</math> The number of <math>n</math>-card Turing machines that halt after exactly or not more than s steps are respectively denoted <math>N(s,n)</math> and <math>G(s,n)</math>.
* Blanking busy beaver: <math>BLB(n,m)</math> is the largest of steps done by any Turing machine with n states and m symbols before blanking the tape.
* [[Beeping Busy Beaver|Beeping busy beaver]]: <math>BBB(n,m)</math> is the largest of steps done by any Turing machine with ''n'' states and ''m'' symbols before [[Quasihalt|quasihalting]].
* Busy periodic beaver: <math>BBP(n,m)</math> is the largest period of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.
* Busy preperiodic beaver: <math>BBS(n,m)</math> is the largest preperiod of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.
* BB<sub>L</sub>(n) (busy beaver for L programs):People have also studied variants with a 2-dimensional tape, or where the tape head is allowed to stay still in addition to moving left or right, etc. More broadly, given any programming language L, whose programs consist of bit-strings, one can define a Busy Beaver function for L-programs:BB<sub>L</sub>(n) := max<sub>P∈L∩{0,1}</sub><sup>≤n</sup><sub>: s(P)<∞</sub>s(P) where s(P) is the number of steps taken by P on a blank input. Alternatively, some people define a “Busy Beaver function for L-programs” using Kolmogorov complexity. That is, they let BB’<sub>L</sub>(n) be the largest integer m such that K<sub>L</sub> (m) ≤ n, where K<sub>L</sub>(m) is the length of the shortest L-program whose output is m on a blank input.<ref name=":3">[https://www.scottaaronson.com/papers/bb.pdf Scott Aaronson - The Busy Beaver frontier]</ref>
* <math>R(n)</math> (The runtime spectrum function): <math>T(n)</math> is the set of <math>n</math>-state Turing machines, and <math>s(M)</math> is the running time of machine <math>M</math> on an all-0 input tape. Let <math>R(n)</math> be the spectrum of possible runtimes of <math>n</math>-state machines on the all-0 input<math> R(n) := \lbrace k \in \natnums : s(M) = k \, \textrm{for} \, \textrm{some} \, M \in T(n) \rbrace</math>.<ref name=":3" />
* Limited Instruction Busy Beaver Function: (main page: [[Limited Instruction Busy Beaver]]) <math> BBi(n)</math> is the longest runtime for all halting n-instruction (allowing any states and symbols) TMs when started on a blank tape.
* Lambda busy beaver: BB<sub>λ</sub>(n) = the maximum normal form size of any closed lambda term of size n
* BLC busy beaver: BB<sub>λ2</sub> = the maximum output size of self-delimiting BLC programs of size n, or 0 if no program of size n exists.
* Terminating Turmite function: (main page: [[Terminating Turmite|Terminating turmites]]) A Terminating Turmite (or Relative Movement Turing Machine) is a 1 dimentional [[Turing machine]] which uses relative directions instead of absolute ones. So instead of moving (L)eft or (R)ight, it (P)roceeds forward (for one step in the same direction as last move or (T)urns-around (move one direction in the opposite direction). TT(n,k) is the maximum steps of all halting n-state, k-symbol Terminating Turmites when started on a blank tape.
* Lazy beaver function: (main page: [[Lazy Beaver|lazy beaver]] ) LB(n, m) is the smallest k such that no n-state, m-symbol [[Turing machine]] halts in exactly k steps.
* Initial busy beaver: (main page: [[Least Busy Beaver|Least busy beaver]]) <math>BB_{init}(n, m, T)</math> Is the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T
* Least busy beaver: <math>BB^{-}(n, m)</math> is the minimal value across all possible starting tapes of <math>BB_{init}(n, m, T)</math>, it is unknown if <math>BB^-(n, m) \ne BB(n, m)</math> for any n or m.
* Dimensional busy beaver DBB(n,m) has 2 inputs n = dimension of the tape, m = number of states. So it computes a Turing machine with m states in a tape with n dimensions. “I” also add the functionality of using a subscript to denote Turing machines of higher levels (ie super Turing machines etc.) So for n = 1,  DBB(1,m) grows at the same speed of BB(n) If we decide to increase the dimensions, say, to two, now we are at a plane of boxes, not just a line.  So that means we can have the tape head move up and down. Though am not sure if it is any more powerful.  We can go up to any dimension, adding possible ways of movement in a state.DBB(n,m) <= BB(m^n)
* <math>\Sigma_{\infty}(n)</math>:<math>\Sigma_{\infty}(n)</math> is defined as the maximal finite output k of an ITTM with at most n non-halting non-limit states given blank input, where they define output to be a natural number k if it is of the form \(\underbrace{11...1}_{k}00...\).They have shown that <math>\Sigma_{\infty}(n)</math> eventually dominates every ITTM-computable function, in analogy to domination property of <math>\Sigma</math>function. Therefore, it is an uncomputably fast-growing function.