Instruction-Limited Busy Beaver: Difference between revisions
(Modified the section describing a key difference between TMs in the BBi contest and the BB contests. In BBi, halting on an undefined transition is an advantage, because it saves us having to add an explicit halting instruction. In traditional BB, this is would be a disadvantage, because we could simply replace the undefined transition with a halting instruction, which allows the TM to take an additional step.) |
(Clarified that we are replacing an undefined transition in a BBi TM with a halting instruction in the equivalent BB TM.) |
||
| Line 1: | Line 1: | ||
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. | 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, 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 will never halt on an undefined transition, but instead will | 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 will never halt on an undefined transition, but instead will replace this with an explicit halting instruction, allowing the machine to take one additional step. | ||
== Champions == | == Champions == | ||
Revision as of 20:25, 19 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, 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 will never halt on an undefined transition, but instead will 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