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 each 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.

Steps Champions

n	BBi(n)	TNF Size	Champions	Notes	Reference
1	1	5	0RH (bbch) 1RH--- (bbch)	BB(1,2)	A384629
2	3	35	0RB---_1LA--- (bbch)		A384629 Shawn
3	5	413	1RB1LB_1LA--- (bbch) (and 13 others)	BB(2,2) - 1	A384629 Shawn
4	16	8,053	1RB---_0RC---_1LC0LA (bbch)		A384629 Shawn
5	37	213,633	1RB2LB---_2LA2RB1LB (bbch)	BB(2,3) - 1	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) - 1, and A BB(3,3) high-ranking machine	A384629 List of long-running BB(3,3) TMs
8	$>6.889\times 10^{1565}$	15,874,490,107	1RB1LA------_1RC3LB1RB---_2LA2LC---0LC (bbch)	Current Champion	nickdrozd Shawn

Symbols Champions

n	Σi(n)	TNF Size	Champions	Notes	Reference
1	1	5	1RH--- (bbch)	Σ(1,2)	A384766
2	2	35	1RB---_1LA--- (bbch) (and 7 others)		A384766 Shawn
3	4	413	1RB1LB_1LA--- (bbch) (and 4 others)	Σ(2,2)	A384766 Shawn
4	5	8,053	1RB0LB---_1LA2RA--- (bbch) (and 40 others)		A384766 Shawn
5	9	213,633	1RB2LB---_2LA2RB1LB (bbch)	Σ(2,3)	A384766 Shawn
6	14	7,363,453	1RB3LA1RA0LA_2LA------3RA (bbch)		A384766 Shawn
7	2,050	312,696,581	1RB2LA1RA1RA_1LB1LA3RB--- (bbch) 1RB2LA1RA_1LC1LA2RB_---1LA--- (bbch)	Σ(2,4), and A Σ(3,3) high-ranking machine	A384766 List of long-running BB(3,3) TMs
8	$>1.355\times 10^{783}$	15,874,490,107	1RB1LA------_1RC3LB1RB---_2LA2LC---0LC (bbch)	Current Champion	nickdrozd Shawn

Notes:

• Proven values for BBi(n) and Σi(n) are shown as bold in the above two tables.
• 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 non-halting). 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 1RH--- (bbch) instead of 1RH (bbch) since this TM references 2 symbols (including the implicit blank symbol 0).

Tree Normal Form (TNF) for BBi

Shown below are the total number of n-instruction Turing machines for each number of instructions n>=0. The numbers of halting and non-halting machines for n=8 are not yet known. The function Tree Normal Form for BBi is denoted BBi_TNF(n)

n	All Machines	All Cumulative	Halting Machines	Halting Cumulative	Non-Halting Machines	Non-Halting Cumulative
0	1	1	1	1	0	0
1	4	5	2	3	2	2
2	30	35	17	20	13	15
3	378	413	260	280	118	133
4	7,640	8,053	5,581	5,861	2,059	2,192
5	205,580	213,633	160,952	166,813	44,628	46.820
6	7,149,820	7,363,453	5,843,696	6,010,509	1,306,124	1,352,944
7	305,333,128	312,696,581	258,044,501	264,055,010	47,288,627	48,641,571
8	15,561,793,526	15,874,490,107	?	?	?	?

Enumeration of Turing machines in Tree Normal Form (TNF) for the Limited-Instruction Busy Beaver problem uses the following procedure:

• The "null Turing machine" with 0 instructions is the root of the tree. This "machine" halts after 0 steps, writing no non-blank symbols to the tape.
• The first instruction starts from A, the implied starting state, reads a 0 on the tape (which is blank at machine start) and must shift right (to avoid consideration of trivial mirror-image machines).
  • This allows the following four possibilities: A0→0RA, A0→0RB, A0→1RA, and A0→1RB. The two machines transitioning to state A never halt, while the two machines transitioning to state B halt. The two halting machines are next expecting an instruction for B0, but since no such instruction exists, the machines halt after a single step.
• Following the enumeration of machines for each previous number of instructions, each of the halting machines is extended from the instruction at which it halted. For n=2, this instruction must be B0. (Non-halting machines cannot be extended since they can never reach a new instruction to be added.)
• As per normal TNF procedure, the new instruction can write any symbol to tape, shift left or right, and transition to any state as long as:
  • The symbol written can be at most one greater than the highest symbol previously read or written, and
  • The state to which the instruction transitions can be at most one state greater than the current maximum state.
• For the BBi problem, any instruction that transitions to a "new" state (one not yet containing any instructions) can be interpreted as a "halting instruction". (e.g. The one-instruction machine A0→1RB is exactly the same as A0→1RH.) Similarly, this new state can be considered a "halt state", as there is functionally no difference between a halt state and an operational state having no instructions. (B = H.)
  • Unlike the traditional BB problem, where a halting instruction is normally used in the last remaining cell in an n x m transition table, it is necessary to consider all possible halting transitions for BBi, (not just those of the form →1RH), as this allows the most possible extensions of n-instruction machines to (n+1)-instruction machines.

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