Instruction-Limited Busy Beaver
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 | 312,696,581 | 1RB2LA1RA1RA_1LB1LA3RB--- (bbch)
|
BB(2,4) champion and
its BB(3,3) doppelganger |
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.
- TNF Size is the total number of TMs enumerated in TNF with n (or fewer) instructions defined.
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