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

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

Certificate:

   (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

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

Certificate:

   (0, 0, 0, 0, 1)    0LB0LC_1RB1LC_1RZ1RA 21
   (1, 0, 0, 0, 1)    0RA1LB_0LB0RC_1RA1RZ 23
   (0, 0, 0, 1, 1)    1RB0LB_1RZ1LC_1RC1RA 22
   (1, 0, 0, 1, 0)    1LA1RB_0LC0RB_0LA1RZ 23
   (1, 0, 0, 1, 1)    0LB1RC_1LA1RZ_0RC0LA 21
   (0, 1, 0, 1, 1)    1RB0RC_1RC0LB_0LA1RZ 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
(1, 0, 0, 0, 0, 0, 1) 0RA0LB_1LC1RZ_0LC1RA 40
(0, 0, 0, 0, 1, 0, 0) 0LB0RB_1RB1LC_1RZ0LA 22
(0, 0, 0, 0, 1, 0, 1) 0LB0RB_1RB1LC_1RZ0LA 22
(1, 0, 0, 0, 1, 0, 0) 0LA1RB_0RB0LC_1LA1RZ 24
(1, 0, 0, 0, 1, 0, 1) 0LA1RB_0RB0LC_1LA1RZ 24
(0, 0, 1, 0, 1, 0, 0) 0RA0RB_1LB1LC_1RA1RZ 21
(0, 0, 1, 0, 1, 0, 1) 0LA0LB_1RB1RC_1LA1RZ 21
(1, 0, 1, 0, 1, 0, 1) 0RB1RZ_0LC0LB_1RA0LA 21

$BB^{-}(2,3)=BB(2,3)=38$

Certificate: https://discord.com/channels/960643023006490684/960643023530762341/1340773779198185607

$BB^{-}(4,2)\geq 50$

Certificate: https://discord.com/channels/960643023006490684/960643023530762341/1340783571501187142