Instruction-Limited Busy Beaver: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
(Modified the equations describing the limits of BBi(2n-1) in relation to BB(2,n) and BB(n,2). BBi(2n-1) is not necessarily as high as BB(2,n) if that BB is the basis for the optimal BBi configuration, since BBi does not include the final halting instruction, where as traditional BB does.)
m (Expanded BB(n) to BB(n,2) to avoid confusion.)
Line 74: Line 74:
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]].
* 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]].
** Similarly, BBi(3) ≥ BB(2,2)-1, BBi(5) ≥ BB(2,3)-1 ≥ BB(3,2)-1, and BBi(7) ≥ BB(2,4)-1 ≥ BB(4). In general, <math display="inline">BBi(2k+1) \geq \max (BB(2,k+1)-1, BB(k+1,2))</math>.
** Similarly, BBi(3) ≥ BB(2,2)-1, BBi(5) ≥ BB(2,3)-1 ≥ BB(3,2)-1, and BBi(7) ≥ BB(2,4)-1 ≥ BB(4,2). In general, <math display="inline">BBi(2k+1) \geq \max (BB(2,k+1)-1, BB(k+1,2))</math>.
** The next subsumed standard Busy Beaver domains are BB(2,5) and BB(5,2), at BBi(9).
** The next subsumed standard Busy Beaver domains are BB(2,5) and BB(5,2), at BBi(9).
* Several BBi(n) champions are also classic BB(a,b) champions but with the final halting transition removed (thus they run for exactly 1 fewer step).
* Several BBi(n) champions are also classic BB(a,b) champions but with the final halting transition removed (thus they run for exactly 1 fewer step).

Revision as of 23:57, 24 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 Instruction-Limited 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, there is no explicit instruction limit and so it is advantageous to use an explicit halting instruction which allows 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)

1RB2LA1RA_1LC1LA2RB_---1LA--- (bbch)

BB(2,4) champion and

its BB(3,3) doppelganger

A384629

List of longrunning BB(3,3) TMs

8 >=119,112,334,170,342,540 15,874,490,011 0RB2LA1RA_1LA2RB1RC_---1LB1LC (bbch) Current BB(3,3) champion 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.
    • Similarly, BBi(3) ≥ BB(2,2)-1, BBi(5) ≥ BB(2,3)-1 ≥ BB(3,2)-1, and BBi(7) ≥ BB(2,4)-1 ≥ BB(4,2). In general, .
    • The next subsumed standard Busy Beaver domains are BB(2,5) and BB(5,2), at BBi(9).
  • Several BBi(n) champions are also classic BB(a,b) champions but with the final halting transition removed (thus they run for exactly 1 fewer step).
  • 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

Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Instruction-Limited_Busy_Beaver&oldid=2589"