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