Instruction-Limited Busy Beaver: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
(A halting instruction is an instruction. BB(4,2) has eight instructions, not 7.)
(Rework the BBi requires solving BB section)
Line 73: Line 73:


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(ab-1) requires solving BB(a,b) since all halting BB(a,b) TMs can be converted into halting (ab-1)-instruction TMs. Furthermore, <math>BBi(ab-1) \ge BB(a,b) - 1</math> (the -1 at the end is because in BB(a,b) the halting transition counts as a step, but in BBi(ab-1) the TM halts as soon as it reaches the undefined transition).
** 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)-1. In general,<math display="inline">\text{BBi}(2k+1) \geq \max ( \text{BB}(2,k+1), \text{BB}(k+1,2)) - 1</math>.
** Thus solving BBi(8) will require solving [[BB(3,3)]] and in particular, it will require solving [[Bigfoot]], which is a [[Cryptids|Cryptid]].
** The next subsumed standard Busy Beaver domains not covered by the above bound are BB(3,4) and BB(4,3), at BBi(11).
** So far, BBi(ab-1) champions are also classic BB(a,b) champions (but with the final halting transition removed) for all a,b ≥ 2 explored so far, but it is not known if this trend will continue.
* 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).
** Beyond the table above we have intrinsic lower bounds: BBi(9) ≥ BB(2,5)-1, BBi(11) ≥ max(BB(2,6),BB(3,4),BB(4,3),BB(6,2))-1.
* 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.
* 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.
* 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.

Revision as of 15:10, 25 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 (albeit an upper bound of nm) 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(ab-1) requires solving BB(a,b) since all halting BB(a,b) TMs can be converted into halting (ab-1)-instruction TMs. Furthermore, (the -1 at the end is because in BB(a,b) the halting transition counts as a step, but in BBi(ab-1) the TM halts as soon as it reaches the undefined transition).
    • Thus solving BBi(8) will require solving BB(3,3) and in particular, it will require solving Bigfoot, which is a Cryptid.
    • So far, BBi(ab-1) champions are also classic BB(a,b) champions (but with the final halting transition removed) for all a,b ≥ 2 explored so far, but it is not known if this trend will continue.
    • Beyond the table above we have intrinsic lower bounds: BBi(9) ≥ BB(2,5)-1, BBi(11) ≥ max(BB(2,6),BB(3,4),BB(4,3),BB(6,2))-1.
  • 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=2597"