Instruction-Limited Busy Beaver: Difference between revisions
(→Champions: BBi(7) champ proven) |
(link BBi(8) to BB(3,3)) |
||
| Line 66: | Line 66: | ||
Notes: | Notes: | ||
* [[ | * Solving BBi(8) will require solving [[BB(3,3)]], because all machines in BB(3,3) contain at most 8 instructions. In particular, solving BBi(8) will require solving [[Bigfoot]], which is a [[Cryptids|Cryptid]]. | ||
* 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. | * TNF Size is the total number of TMs enumerated in [[TNF]] with n (or fewer) instructions defined. | ||
Revision as of 04:23, 23 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:
- Solving BBi(8) will require solving BB(3,3), because all machines in BB(3,3) contain at most 8 instructions. In particular, solving BBi(8) will require solving Bigfoot, which is a Cryptid.
- 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.
- BBi(n) ≥ n. A halting (n+1) x 1 TM that chains all its states together (A0 = 0RB, B0 = 0RC, C0 = 0RD, ...) through the penultimate TM state will take n steps to pass through all states exactly once (a repeat would guarantee nonhalting). The penultimate state, the nth state, puts the TM into n+1st state, which is undefined and does not count as a step.
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