Instruction-Limited Busy Beaver: Difference between revisions
(Added the definition of Σi(n), the non-blank symbols function for n-instruction TMs.) |
(language edits) |
||
| Line 1: | Line 1: | ||
An '''n-instruction Turing machine''' is a [[Turing machine]] with an arbitrary number of states and symbols, but | 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, which is necessary in the BBi problem in order to minimize the number of instructions. In the traditional BB problem, which is not instruction-limited, a TM | A TM is considered to halt as soon as it reaches an undefined transition, which is necessary in the BBi problem in order to minimize the number of instructions. In the traditional BB problem, which is not instruction-limited, 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:07, 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, which is necessary in the BBi problem in order to minimize the number of instructions. In the traditional BB problem, which is not instruction-limited, 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