Instruction-Limited Busy Beaver

An n-instruction Turing machine is a Turing machine having an arbitrary number of states and symbols, but having only n defined transitions/instructions in its transition table (all others are undefined).

An Instruction-Limited Busy Beaver is any n-instruction Turing machine taking the maximum number of steps (BBi(n)) after starting from an initially blank tape before eventually halting, over all possible n-instruction Turing machines.

Similarly, an Instruction-Limited Symbols Busy Beaver is any n-instruction Turing machine writing the most non-blank symbols (Σi(n)) to the tape before halting, over all possible n-instruction Turing machines.

An Instruction-Limited Busy Beaver Competition (or "game") is a contest to find, for a given n, the value of either BBi(n) or Σi(n).

The Instruction-Limited Busy Beaver Sequences list the values for BBi(n) and Σi(n) for n=0, 1, 2, ....

• The currently known values of BBi(n) for n>=0 are: 0, 1, 3, 5, 16, 37, 123, 3932963, .... BBi(8) is at least 6.889 x 10¹⁵⁶⁵, which is the number of steps taken by the current 8-instruction champion machine, discovered by Nick Drozd.
• The currently known values of Σi(n) for n>=0 are: 0, 1, 2, 4, 5, 9, 14, 2050, .... Σi(8) is at least 1.355 x 10⁷⁸³, which is the number of non-blank symbols written to tape by the same 8-instruction champion machine.

As with the traditional Busy Beaver sequences, BBi(n) and Σi(n) are both uncomputable, with both growing faster than any computable function.

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.

Motivation

The goal of the original Busy Beaver contest, introduced by Tibor Radó, was to find a halting Turing machine of a given size that, when started on a blank tape, either runs for the longest number of steps (BB(n)), or which prints the largest number of 1’s to tape before halting (Σ(n)) [1]. Originally, the contests considered only two-symbol Turing machines (0,1), so both the steps sequence (BB(1), BB(2), BB(3), ...) and the symbols sequence (Σ(1), Σ(2), Σ(3), ...) were functions of a single variable n, the number of states.

The Busy Beaver contest was later generalized to m-symbol machines (0,1,2,…,m-1), so each contest for n states and m symbols has its own values for maximum steps (BB(n,m)), and for non-blank symbols written to tape (Σ(n,m)). While this adds more interesting individual contests, it does split the focus among different possible sequences. For example, it is natural to compare the original steps sequence (BB(n,2) for n=1, 2, 3, ...) with the steps sequence for 2-state, m-symbol Turing machines (BB(2,m) for m=1, 2, 3, ...).

The Instruction-Limited Busy Beaver concept was primarily motivated by the goal of uniting the various Busy Beaver contests into a single sequence defined not by the maximum number of states and symbols (BB(n,m)), but rather by the number of instructions (BBi(n)). Furthermore, counting the number of instructions in a Turing machine is arguably a simpler way of defining a “machine of a given size” than is considering the numbers of states and symbols in its state table.

A champion n-instruction Busy Beaver machine may lie within any a x b domain, and it may share the same number of steps and symbols written as a machine from a different domain altogether. For example, it was discovered that two different 7-instruction Turing machines take 3,932,963 steps and write 2,050 non-blank symbols, but one of these is a 2-state, 4-symbol machine with one undefined transition, while the other is a 3-state, 3-symbol machine with two undefined transitions.

It is currently unknown what the state table shapes of BBi(n) champions for n>=8 will be. When n = a*b-1 for some a,b >=2, will BBi(n) be one less than one of the original values of BB(a,b)? Or will a more sparsely populated state table with a larger product of states and symbols be able to generate an even longer run time using n instructions? The current BBi(8) champion is a 3-state, 4-symbol machine, but this may still be surpassed by a 3-state, 3-symbol machine yet to be found.

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	$>6.889\times 10^{1565}$	15,874,490,107	1RB1LA------_1RC3LB1RB---_2LA2LC---0LC (bbch)	Current Champion	nickdrozd Shawn

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, $BBi(ab-1)\geq BB(a,b)-1$ (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.
• The convention for writing TMs in standard text format here is to include as many states and symbols as are referenced. So for example, we write 1RB---_------ (bbch) instead of 1RB (bbch) since this TM references 2 states and 2 symbols (including the implicit start state A and blank symbol 0).

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