User:Qwerpiw/List of BB functions

• Maximum space: Ben-Amram call this $space(n)$, bbchallenge calls it BB_SPACE(n) or $BB_{space}(n)$. 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.
• Maximum consecutive ones: Ben-Amram calls this $num(n)$. A TM only qualifies if it halts with all ones consecutive on tape.
• $N_{e}$ function: Radó formulated the number of halting machines in terms of the set of all valid busy beaver entries $M,s$ where $M$ is the Turing machine, and $s$ is the exact number of steps the halting Turing machine took. The set of all halting $n$-card machines is denoted $E_{n}$, and the cardinality of this set is denoted $N_{e}(n)$ The number of $n$-card Turing machines that halt after exactly or not more than s steps are respectively denoted $N(s,n)$ and $G(s,n)$.
• Blanking busy beaver: $BLB(n,m)$ is the largest of steps done by any Turing machine with n states and m symbols before blanking the tape.
• Beeping busy beaver: $BBB(n,m)$ is the largest of steps done by any Turing machine with n states and m symbols before quasihalting.
• Busy periodic beaver: $BBP(n,m)$ is the largest period of any cycler or translated cycler with n states and m symbols.
• Busy preperiodic beaver: $BBS(n,m)$ is the largest preperiod of any cycler or translated cycler with n states and m symbols.
• BB_L(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_L(n) := max_{P∈L∩{0,1}}^≤n_{: s(P)<∞}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’_L(n) be the largest integer m such that K_L (m) ≤ n, where K_L(m) is the length of the shortest L-program whose output is m on a blank input.
• $R(n)$ (The runtime spectrum function): $T(n)$ is the set of $n$-state Turing machines, and $s(M)$ is the running time of machine $M$ on an all-0 input tape. Let $R(n)$ be the spectrum of possible runtimes of $n$-state machines on the all-0 input$R(n):=\lbrace k\in \mathbb {N} :s(M)=k\,{\textrm {for}}\,{\textrm {some}}\,M\in T(n)\rbrace$.
• Limited Instruction Busy Beaver Function: (main page: Limited Instruction Busy Beaver) $BBi(n)$ 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_λ(n) = the maximum normal form size of any closed lambda term of size n
• BLC busy beaver: BB_λ2 = 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 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 ) 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) $BB_{init}(n,m,T)$ Is the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T
• Least busy beaver: $BB^{-}(n,m)$ is the minimal value across all possible starting tapes of $BB_{init}(n,m,T)$, it is unknown if $BB^{-}(n,m)\neq BB(n,m)$ 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)
• $\Sigma _{\infty }(n)$:$\Sigma _{\infty }(n)$ 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 $\Sigma _{\infty }(n)$ eventually dominates every ITTM-computable function, in analogy to domination property of $\Sigma$function. Therefore, it is an uncomputably fast-growing function.