View source for Instruction-Limited Busy Beaver

An '''n-instruction Turing machine''' is a [[Turing machine]] with an arbitrary number of states and symbols, but only ''n'' defined transitions/instructions in its transition table (all others are undefined). The '''Limited Instruction Busy Beaver''' (BBi(n)) problem is the Busy Beaver problem limited to n-instruction TMs. BBi(n) is the longest runtime for all halting n-instruction TMs when started on a blank tape and Σi(n) is the maximum number of non-blank symbols written by an n-instruction TM when halting and when started on a blank tape.

A TM is considered to halt as soon as it reaches an undefined transition. This convention reduces the number of instructions for a BBi Turing machine. In the traditional BB(n,m) problem, which is instruction-limited to nm, if a TM is to halt when reaching an undefined transition, we replace this with an explicit halting instruction, allowing the machine to take one additional step.

== Champions ==
{| class="wikitable"
!n
!BBi(n)
!TNF Size
!Champions
!Notes
!Reference
|-
| style="text-align: right;" | 1
| style="text-align: right;" | 1
| style="text-align: right;" | 5
|{{TM|0RB_---}} {{TM|1RB---_------}}
|
|[[oeis:A384629|A384629]]
|-
| style="text-align: right;" | 2
| style="text-align: right;" | 3
| style="text-align: right;" | 35
|{{TM|0RB---_1LA---}}
|
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716114952818829 Shawn]
|-
| style="text-align: right;" | 3
| style="text-align: right;" | 5
| style="text-align: right;" | 413
|{{TM|1RB1LB_1LA---}} (and 13 others)
|[[BB(2)]] champion
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716181214564353 Shawn]
|-
| style="text-align: right;" | 4
| style="text-align: right;" | 16
| style="text-align: right;" | 8,053
|{{TM|1RB---_0RC---_1LC0LA}}
|
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716260587700447 Shawn]
|-
| style="text-align: right;" | 5
| style="text-align: right;" | 37
| style="text-align: right;" | 213,633
|{{TM|1RB2LB---_2LA2RB1LB}}
|[[BB(2,3)]] champion
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716514234040341 Shawn]
|-
| style="text-align: right;" | 6
| style="text-align: right;" | 123
| style="text-align: right;" | 7,363,453
|{{TM|1RB3LA1RA0LA_2LA------3RA}}
|
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393768821478785207 Shawn]
|-
| style="text-align: right;" | 7
| style="text-align: right;" | 3,932,963
| style="text-align: right;" | 312,696,581
|{{TM|1RB2LA1RA1RA_1LB1LA3RB---}}
{{TM|1RB2LA1RA_1LC1LA2RB_---1LA---}}
|[[BB(2,4)]] champion and 
its [[BB(3,3)]] doppelganger
|[[oeis:A384629|A384629]] 
[https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/3x3 List of longrunning BB(3,3) TMs]
|}
Notes:

* Solving BBi(8) will require solving [[BB(3,3)]], because all machines in BB(3,3) contain at most 8 instructions. In particular, solving BBi(8) will require solving [[Bigfoot]], which is a [[Cryptids|Cryptid]].
* Several BBi(n) champions are also classic BB(a,b) champions but with the final halting transition removed.
* TNF Size is the total number of TMs enumerated in [[TNF]] with n (or fewer) instructions defined.
* BBi(n) ≥ n. A halting (n+1) x 1 TM that chains all its states together (A0 = 0RB, B0 = 0RC, C0 = 0RD, ...) through the penultimate TM state will take n steps to pass through all states exactly once (a repeat would guarantee nonhalting). The penultimate state, the nth state, puts the TM into n+1st state, which is undefined and does not count as a step.

== See Also ==
* OEIS list of BBi(n) values: https://oeis.org/A384629
* OEIS list of Σi(n) values: https://oeis.org/A384766
* Discussion on Discord: https://discord.com/channels/960643023006490684/960643023530762341/1393697378657374290