Instruction-Limited Busy Beaver: Difference between revisions
m (→Champions: Align numbers in table.) |
(mathematical language change) |
||
| Line 1: | Line 1: | ||
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. | 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 | 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 == | == Champions == | ||
Revision as of 19:24, 22 July 2025
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
| n | BBi(n) | TNF Size | Champions | Notes | Reference |
|---|---|---|---|---|---|
| 1 | 1 | 5 | 0RB_--- (bbch) 1RB---_------ (bbch)
|
A384629 | |
| 2 | 3 | 35 | 0RB---_1LA--- (bbch)
|
A384629 Shawn | |
| 3 | 5 | 413 | 1RB1LB_1LA--- (bbch) (and 13 others)
|
BB(2) champion | 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