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 10⁷⁸³	15,874,490,107	`1RB1LA------_1RC3LB1RB---_2LA2LC---0LC` (bbch)	Current 3x4 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, $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.
- 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.

Instruction-Limited Busy Beaver

Motivation

Champions

See Also

Navigation menu