Least Busy Beaver

The least busy beaver $BB^{-}(n,m)$ problem is a variation of the busy beaver problem which considers TM behavior across all starting tapes (not just blank tapes like the traditional BB problem) discovered by Racheline on 15 Feb 2025.

Definition

Let $BB_{init}(n,m,T)$ be the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T (where T is allowed to be any infinite tape configuration, including ones with an infinite number of non-zero values). Then

$$BB^{-}(n,m)=min_{T}BB_{init}(n,m,T)$$

In other words, the minimal value across all possible starting tapes. This minimum must exist because the values of $BB_{init}(n,m,T)$ are all positive integers and thus well ordered.

Note that $BB_{init}(n,m,B)=BB(n,m)$ where B is the blank (all-zeros) tape. Therefore,

$$BB^{-}(n,m)\leq BB(n,m)$$

We have not yet found an example where we can prove that $BB^{-}(n,m)\neq BB(n,m)$.

Known Results

Clearly, $BB^{-}(1,m)=1$ for all positive integers $m$, since $BB_{init}(n,m,T)$ is always at least $1$ so we have $1\leq BB^{-}(1,m)\leq BB(1,m)=1$.

Small least busy beaver values

	2-state	3-state	4-state
2-symbol	$BB^{-}(2)=6$	$BB^{-}(3)=21$	$BB^{-}(4)=107$
3-symbol	$BB^{-}(2,3)=38$

Racheline proved by hand that $BB^{-}(2,2)=6$, and with the help of computer searches, she proved $BB^{-}(3,2)=21$. She later made a program that automatically tries to confirm lower bounds $BB^{-}(n,m)\geq t$, by covering the set of all initial tapes with a family of sets, where each set of the family contains tapes that agree in a given radius around the starting position, such that a single TM halts in $\geq t$ steps without leaving that shared part of the tapes (and therefore halts in $\geq t$ steps on all of those tapes with the same transition history). This program verified her previous results and produced the results $BB^{-}(2,3)=BB(2,3)=38$, and later $BB^{-}(4,2)=107$ using Shawn Ligocki's idea to speed up the process by first using TMs that are likely to halt late (such as the TMs listed in BB(4)) to filter out most tapes. None of this has been formally verified as of 16 Feb 2025.

Certificate of $BB^{-}(2,2)=BB(2,2)=6$:

   (0, 0, 0)    1RB1RZ_0LB1LA 6
   (0, 0, 1)    0LB1RZ_1RA0RB 6
(0, 1, 0, 1, 0) 0RA0RB_0LB1RZ 6
(0, 1, 0, 1, 1) 0LA0LB_0RB1RZ 6
(1, 1, 0, 1, 1) 0RB1RZ_0LB0LA 7

Certificate of $BB^{-}(3,2)=BB(3,2)=21$:

   (0, 0, 0, 0, 1)    0LB0LC_1RB1LC_1RZ1RA 21
   (0, 0, 0, 1, 1)    1RB0LB_1RZ1LC_1RC1RA 22
   (0, 1, 0, 1, 1)    1RB0RC_1RC0LB_0LA1RZ 21
   (1, 0, 0, 0, 1)    0RA1LB_0LB0RC_1RA1RZ 23
   (1, 0, 0, 1, 0)    1LA1RB_0LC0RB_0LA1RZ 23
   (1, 0, 0, 1, 1)    0LB1RC_1LA1RZ_0RC0LA 21
   (1, 1, 0, 1, 1)    0RB0LB_1RZ1LC_1RA0RC 21
(0, 0, 0, 0, 0, 0, 0) 1RB1RZ_1LB0RC_1LC1LA 21
(0, 0, 0, 0, 0, 0, 1) 0LB1RZ_0LC1RB_1RA0RC 24
(0, 0, 0, 0, 1, 0, 0) 0LB0RB_1RB1LC_1RZ0LA 22
(0, 0, 0, 0, 1, 0, 1) 0LB0RB_1RB1LC_1RZ0LA 22
(0, 0, 1, 0, 1, 0, 0) 0RA0RB_1LB1LC_1RA1RZ 21
(0, 0, 1, 0, 1, 0, 1) 0LA0LB_1RB1RC_1LA1RZ 21
(1, 0, 0, 0, 0, 0, 1) 0RA0LB_1LC1RZ_0LC1RA 40
(1, 0, 0, 0, 1, 0, 0) 0LA1RB_0RB0LC_1LA1RZ 24
(1, 0, 0, 0, 1, 0, 1) 0LA1RB_0RB0LC_1LA1RZ 24
(1, 0, 1, 0, 1, 0, 1) 0RB1RZ_0LC0LB_1RA0LA 21