Editing Busy beaver (section)

== Generalizations ==
Analogs of the shift function can be simply defined in any programming language, given that the programs can be described by bit-strings, and a program's number of steps can be counted.<ref name=":5">{{Cite web |last=Aaronson |first=Scott |date=2024-07-02 |title=BusyBeaver(5) is now known to be 47,176,870 |url=https://scottaaronson.blog/?p=8088 |access-date=2024-07-04 |website=Shtetl-Optimized |language=en-US}}</ref> For example, the busy beaver game can also be generalized to two dimensions using Turing machines on two-dimensional tapes, or to Turing machines that are allowed to stay in the same place as well as move to the left and right.<ref name=":5" /> Alternatively a "busy beaver function" for diverse models of computation can be defined with [[Kolmogorov complexity]].<ref name=":5" /> This is done by taking <math>{BB}(n)</math> to be the largest integer <math>m</math> such that <math>K_L(m) \le n</math>, where <math>K_L(m)</math> is the length of the shortest program in <math>L</math> that outputs <math>m</math>: <math>{BB}(n)</math> is thereby the largest integer a program with length <math>n</math> or less can output in <math>L</math>.<ref name=":5" />

The longest running 6-state, 2-symbol machine which has the additional property of reversing the tape value at each step produces {{val|6147}} 1s after {{val|47339970}} steps.{{Citation needed|date=February 2022}} So for the Reversal Turing Machine (RTM) class,<ref>{{Cite web |title=Reversal Turing machine |url=https://skelet.ludost.net/bb/RTM.htm |access-date=2022-02-10 |website=skelet.ludost.net}}</ref> ''S''<sub>RTM</sub>(6) ≥ {{val|47339970}} and Σ<sub>RTM</sub>(6) ≥ {{val|6147}}. Likewise we could define an analog to the Σ function for [[register machine]]s as the largest number which can be present in any register on halting, for a given number of instructions.{{Citation needed|date=June 2024}}

=== Different numbers of symbols ===
A simple generalization is the extension to Turing machines with ''m'' symbols instead of just two (0 and 1).<ref name=":5" /> For example a trinary Turing machine with ''m'' = 3 symbols would have the symbols 0, 1, and 2. The generalization to Turing machines with ''n'' states and ''m'' symbols defines the following '''generalized busy beaver functions''':
# Σ(''n'', ''m''): the largest number of non-zeros printable by an ''n''-state, ''m''-symbol machine started on an initially blank tape before halting,{{Citation needed|date=June 2024}} and
# ''S''(''n'', ''m''): the largest number of steps taken by an ''n''-state, ''m''-symbol machine started on an initially blank tape before halting.<ref name=":5" />

For example, the longest-running 3-state 3-symbol machine found so far runs {{val|119112334170342540}} steps before halting<!--[https://cse.unr.edu/~al/BusyBeaver.html]-->.<ref name="michel_comp" /><ref>{{cite journal|last=Michel|first=Pascal|date=2015-12-14|title=Problems in number theory from busy beaver competition|journal=Logical Methods in Computer Science|volume=11|issue=4|page=10}}</ref>

=== Nondeterministic Turing machines ===
{| class="wikitable" align="right"
|+ Maximal halting times and states from ''p''-case, 2-state, 2-color NDTM<ref name="NDTM">{{cite web |last1=Wolfram |first1=Stephen |author-link=Stephen Wolfram |date=4 February 2021 |title=Multiway Turing Machines |url=https://wolframphysics.org/bulletins/2021/02/multiway-turing-machines/ |website=www.wolframphysics.org |language=en |access-date=7 July 2022 |archive-date=7 July 2022 |archive-url=https://web.archive.org/web/20220707080645/https://wolframphysics.org/bulletins/2021/02/multiway-turing-machines/ |url-status=live }}</ref>
! p
! steps
! states
|-
! 1
| 2 || 2
|-
! 2
| 4 || 4
|-
! 3
| 6 || 7
|-
! 4
| 7 || 11
|-
! 5
| 8 || 15
|-
! 6
| 7 || 18
|-
! 7
| 6 || 18
|}

The problem can be extended to [[nondeterministic Turing machine]]s by looking for the system with the most states across all branches or the branch with the longest number of steps.<ref name="NDTM" /> The question of whether a given NDTM will halt is still computationally irreducible, and the computation required to find an NDTM busy beaver is significantly greater than the deterministic case, since there are multiple branches that need to be considered. For a 2-state, 2-color system with ''p'' cases or rules, the table to the right gives the maximum number of steps before halting and maximum number of unique states created by the NDTM.