Instruction-Limited Busy Beaver: Difference between revisions
Jump to navigation
Jump to search
(Add table of champions) |
m (→Champions) |
||
| Line 65: | Line 65: | ||
* [[Bigfoot]] is an 8-instruction TM, so solving BBi(8) or higher will require solving [[Cryptids]]. | * [[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. | * 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 == | == See Also == | ||
Revision as of 02:15, 17 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.
- 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