Instruction-Limited Busy Beaver: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
(Created page with "An '''n-instruction Turing machine''' is a Turing machine with an arbitrary number of states and symbols, but limited to 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. So BBi(n) is the longest runtime for all halting n-instruction TMs when started on a blank tape. A TM is considered to halt as soon as it...")
 
(Add table of champions)
Line 2: Line 2:


A TM is considered to halt as soon as it reaches an undefined transition (unlike in the traditional Busy Beaver problem where the TM must make an explicit halting transition which adds one more step).
A TM is considered to halt as soon as it reaches an undefined transition (unlike in the traditional Busy Beaver problem where the TM must make an explicit halting transition which adds one more step).
== Champions ==
{| class="wikitable"
!n
!BBi(n)
!TNF Size
!Champion
!Notes
!Reference
|-
|1
|1
|5
|{{TM|1RB---_------}}
|(and one other)
|[[oeis:A384629|A384629]]
|-
|2
|3
|35
|{{TM|0RB---_1LA---}}
|
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716114952818829 Shawn]
|-
|3
|5
|413
|{{TM|1RB1LB_1LA---}}
|[[BB(2)]] champion (and 13 others)
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716181214564353 Shawn]
|-
|4
|16
|8,053
|{{TM|1RB---_0RC---_1LC0LA}}
|
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716260587700447 Shawn]
|-
|5
|37
|213,633
|{{TM|1RB2LB---_2LA2RB1LB}}
|[[BB(2,3)]] champion
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393716514234040341 Shawn]
|-
|6
|123
|7,363,453
|{{TM|1RB3LA1RA0LA_2LA------3RA}}
|
|[[oeis:A384629|A384629]] [https://discord.com/channels/960643023006490684/960643023530762341/1393768821478785207 Shawn]
|-
|7
|≥3,932,963
|
|{{TM|1RB2LA1RA1RA_1LB1LA3RB---}}
|[[BB(2,4)]] champion
|[[oeis:A384629|A384629]]
|}
Notes:
* [[Bigfoot]] is an 8-instruction TM, so solving BBi(8) or higher will require solving [[Cryptids]].
* Several BBi(n) champions are also classic BB(a,b) champions but with the final halting transition removed.


== See Also ==
== See Also ==

Revision as of 23:37, 16 July 2025

An n-instruction Turing machine is a Turing machine with an arbitrary number of states and symbols, but limited to 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. So BBi(n) is the longest runtime for all halting n-instruction TMs when started on a blank tape.

A TM is considered to halt as soon as it reaches an undefined transition (unlike in the traditional Busy Beaver problem where the TM must make an explicit halting transition which adds one more step).

Champions

n BBi(n) TNF Size Champion Notes Reference
1 1 5 1RB---_------ (bbch) (and one other) A384629
2 3 35 0RB---_1LA--- (bbch) A384629 Shawn
3 5 413 1RB1LB_1LA--- (bbch) BB(2) champion (and 13 others) A384629 Shawn
4 16 8,053 1RB---_0RC---_1LC0LA (bbch) A384629 Shawn
5 37 213,633 1RB2LB---_2LA2RB1LB (bbch) BB(2,3) champion A384629 Shawn
6 123 7,363,453 1RB3LA1RA0LA_2LA------3RA (bbch) A384629 Shawn
7 ≥3,932,963 1RB2LA1RA1RA_1LB1LA3RB--- (bbch) BB(2,4) champion A384629

Notes:

  • Bigfoot is an 8-instruction TM, so solving BBi(8) or higher will require solving Cryptids.
  • Several BBi(n) champions are also classic BB(a,b) champions but with the final halting transition removed.

See Also

Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Instruction-Limited_Busy_Beaver&oldid=2520"