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

The Instruction-Limited Busy Beaver function (BBi(n)) is the maximum steps taken by any n-instruction Turing machines before eventually halting (when started on an initially blank tape). Similarly, the Instruction-Limited Symbols Busy Beaver function (Σi(n)) is the maximum sigma score (number of non-blank symbols left on the tape at halting) for all halting n-instruction Turing machines (when started on an initially blank tape).

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.

Champions

n	BBi(n)	Step Champions	Notes	Reference
1	1	`0RH` (bbch) `1RH---` (bbch)	BB(1,2)	A384629
2	3	`0RB---_1LA---` (bbch)		A384629 Shawn
3	5	`1RB1LB_1LA---` (bbch) (and 13 others)	BB(2,2) - 1	A384629 Shawn
4	16	`1RB---_0RC---_1LC0LA` (bbch)		A384629 Shawn
5	37	`1RB2LB---_2LA2RB1LB` (bbch)	BB(2,3) - 1	A384629 Shawn
6	123	`1RB3LA1RA0LA_2LA------3RA` (bbch)		A384629 Shawn
7	3,932,963	`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}$	`1RB1LA------_1RC3LB1RB---_2LA2LC---0LC` (bbch)	Current Champion	nickdrozd Shawn

n	Σi(n)	Sigma Champions	Notes	Reference
1	1	`1RH---` (bbch)	Σ(1,2)	A384766
2	2	`1RB---_1LA---` (bbch) (and 7 others)		A384766 Shawn
3	4	`1RB1LB_1LA---` (bbch) (and 4 others)	Σ(2,2)	A384766 Shawn
4	5	`1RB0LB---_1LA2RA---` (bbch) (and 40 others)		A384766 Shawn
5	9	`1RB2LB---_2LA2RB1LB` (bbch)	Σ(2,3)	A384766 Shawn
6	14	`1RB3LA1RA0LA_2LA------3RA` (bbch)		A384766 Shawn
7	2,050	`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}$	`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$ $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. With the BBi(8) champion it appears that this trend has been broken (it is believed that $BB(3,3)<10^{1565}$ )
- 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.
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). If one state has no instructions leaving it, the convention is to treat it as the halt state H.

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

Domain-Restricted BBi

In addition to the standard Instruction-Limited Busy Beaver function BBi(n), where the numbers of states and symbols a Turing machine may have is unlimited, it may also be useful to consider the “Domain-Restricted BBi”, where the numbers of instructions, states, and/or symbols are specified values or ranges.

Following are some example three-argument functions within the Domain-Restricted BBi. For each function, the value is always the greatest number of steps taken by a Turing machine satisfying the corresponding restrictions:

BBi(i, n, m): An n-state, m-symbol Turing machine having i instructions
BBi(i, <=n, m): An i-instruction, m-symbol Turing machine having no greater than n states
BBi(i, -, m): An i-instruction, m-symbol Turing machine having any number of states
BBi(i, n, <=m): An i-instruction, n-state Turing machine having no greater than m instructions
Etc.

Note that we have replaced the argument n from the standard BBi function with i in this three-argument version, primarily to avoid confusion with the n normally used to denote the number of states in a standard BB Turing machine.

For each of the three arguments, we may simply list a value, in which case the Turing machine must have exactly that number of instructions, states, or symbols. Another option is to specify a range, such as “<=n”, or “<=m”, in which case the Turing machine must have n or fewer states, or m or fewer symbols, respectively. And the final option is to give an argument as “-“, in which case, there is no restriction to the Turing machine’s number of instructions, states, or symbols.

Example Questions:

The main reason for having the flexibility in the way that the arguments are presented within the Domain-Restricted BBi function is that some problems relating to BB and BBi are best suited to examining Turing machines having specific numbers of states and symbols, while others are more practically examined within a range of state and symbol values instead. For example, consider the following two questions, along with two possible ways to interpret and answer each question:

Question 1: What are the maximum numbers of steps an i-instruction, 5-state, 2-symbol Turing machine can take before halting?

Interpretation #1: For i=1 through 10, BBi(i, 5, 2) = -, -, -, -, 9, 31, 65, 793, 47176869, 47176870. In this interpretation, there are no values for 1<=i<=4, because there is no way to construct a 5-state Turing machine using fewer than 5 instructions. Also, the values for i=5, 6, and 7 are lower than those in the following second interpretation.
Interpretation #2: For i=1 through 10, BBi(i, <=5, 2) = 1, 3, 5, 16, 20, 37, 106, 793, 47176869, 47176870. For this interpretation, we do not take the question’s wording of “5-state” so literally, but rather we allow the consideration of any Turing machine having no greater than 5 states. For example, BBi(7, <=5, 2) = 106 = BB(4,2) – 1.

The second interpretation, despite being less literally adherent to the question wording than the first, seems more useful for this particular question, specifically because we are probably interested in seeing how the number of steps grows for the best possible arrangement of i instructions within the 5 x 2 state table, and not just among the arrangements that specifically include defined transitions for all five states.

Question 2: For all n>1, will the 2n-1 instruction, n-state, 2-symbol BBi champion (one undefined transition) always exceed the 2n-1 instruction, n+1 state, 2-symbol BBi champion (3 undefined transitions)? (This is currently conjectured to be false.)

Interpretation #1: Compare values of BBi(2n-1, n, 2) with those of BBi(2n-1, n+1, 2) for n=2 through 5:
- For n=2 through 5, BBi(2n-1, n, 2) = 5, 20, 106, 47176869.
- For n=2 through 5, BBi(2n-1, n+1, 2) = 4, 19, 65, ???.
Interpretation #2: Compare values of BBi(2n-1, <=n, 2) with those of BBi(2n-1, <=n+1, 2) for n=2 through 5:
- For n=2 through 5, BBi(2n-1, <=n, 2) = 5, 20, 106, 47176869.
- For n=2 through 5, BBi(2n-1, <=n+1, 2) = 5, 20, 106, ???.

For this second question, the first interpretation clearly seems to be the more useful one, as we are probably interested in comparing the steps differences between machines having strictly n states (with one undefined transition) with machines having strictly n+1 states (with three undefined transitions). Using the second interpretation, information about these steps differences is lost since we have replaced the steps values of the machines with n+1 states with the values from the stronger n-state machines.

Selected Results:

Following are some results for Domain-Restricted BBi, some of which follow logically from their definitions, and others which have been computed so far:

BBi(i, -, -) = BBi(i). If we allow any number of states and symbols, then this is the standard BBi function.
BBi(-, n, m) = BBi(nm, n, m) = BB(n, m) for n>=2, m>=2. If we allow any number of instructions, or if we specify nm instructions, then this is equivalent to the standard BB(n, m) function.
BBi(nm-1, n, m) = BBi(nm, n, m) - 1 = BB(n, m) - 1 for n>=2, m>=2. With one undefined transition, the number of steps is one less than having a completely filled n x m transition table including a halting instruction, which adds one final step.
For i>=1, BBi(i, -, 2) = 1, 3, 5, 16, 20, 37, 106, 793, …. BBi(9, -, 2) is at least 47176869, but it may be even larger if a more powerful 6-state, 2-symbol machine having three undefined transitions can be found. BBi(10, -, 2) will almost certainly be greater than the current lower bound of 47176870 = BB(5,2).
For i>=1, BBi(i, <=2, -) = 1, 3, 5, 13, 37, 123, 3232963, …. The number of states is specified here as “<=2” rather than “2” so that we can have a valid value for one instruction. (A 1-instruction Turing machine has only one operating state.) BBi(8, <=2, -) will almost certainly be greater than the current lower bound of 3232964 = BB(2,4).