Instruction-Limited Busy Beaver

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.

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? This is just one of the many questions that motivated the instruction-limited Busy Beaver contest.

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	>1.355 x 10783	15,874,490,107	1RB1LA------_1RC3LB1RB---_2LA2LC---0LC (bbch)	A 3x4 Turing machine Given bound is Σi(8) < BBi(8)	nickdrozd

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.
• Estimate of number of steps for the current BBi(8) champion is not currently known, but must be greater than the number of symbols written to tape Σi(8), which is approximately 1.355 x 10⁷⁸³. The true value for the current BBi(8) champion is likely around the square of the symbols value (e.g. ~10¹⁵⁶⁶).

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