A variant of the Busy Beaver function

Question

Set $BB(k,n)$ to be the same definition as the Busy Beaver but where one is looking at all $n$-state machines, and the transition graph has at most $k$ "write 1" instructions. This may be a natural thing to look at because Nick Drozd has conjectured that roughly in general Busy Beaver machines should have more "write 1" instructions than "write 0." I initially conjectured that for any $k$, there will be a computable function $f_k(n)$ such that for all $n$, $BB(k,n) \le f_k(n)$. This is in fact true for $k=1$. And if this is true, it is barely true, since $BB(2n,n)=BB(n)$ so the $f_k(n)$ would need to have their values be very fast growing. Note also that the order of the quantifiers is important: $f_k(n)$ is a function which is chosen, after $k$. However, in this thread on Scott Aaronson's blog, Ben pointed out the following.

Theorem: Given an axiom system that formalizes arithmetic, there is a finite $K$ such that if it can prove a computable upper bound to $BB(k, n)$ for any $k > K$, then it is inconsistent.

This doesn't disprove the existence of computable $f_k(n)$, but it does seem to make them unlikely. So based on this my question is:

1. For which $k$ are there computable $f_k(n)$?

Right now, it is plausible that even for $k=3$ there is no computable $f_k(n)$ of this sort.

Answer 1

Just some details for my comment. Your initial conjecture is false: for all but finitely many $k$, $\mathrm{BB}(k, n)$ is not dominated by any computable function.

Let $U$ be a universal Turing machine with $m$ states and $u$ write-$1$ instructions. Let $T$ be a Turing machine with $\ell$ states and $t$ write-$1$ instructions, such that on input $0^i 1$, $T$ writes the $i$th binary word $w$ on tape, walks to the beginning of the tape, and halts.

Now route the halting state of $T$ to the initial state of $U$. You get a Turing machine $T' = U \circ T$ with at most $\ell + m$ states and $t + u$ write-$1$ instructions, which we can use to simulate any other Turing machine by using suitable unary inputs.

So now if $f$ is a computable function, then there exists a word $w$ of length $s$ that codes (for the UTM $U$) a Turing machine that, given $n$ in binary, counts to $\sum_{i \leq 2^{2^n}} f(i)$ and then halts. With a string of about $2^{O(s n)}$ many zeroes followed by a $1$, we can then make $T'$ simulate the computation of $U$ on input $(w, n)$.

We can write down any word of the form $0^{2^{O(s n)}} 1$ with $2^{c s n}$ states for a constant $c$, just have a state for each $0$, and we need only a single write-$1$ instruction, so we get $\mathrm{BB}(1 + t + u, 2^{c n s} + \ell + m) > \max_{j \leq 2^{2^n}} f(j)$.

In particular $\mathrm{BB}(1 + t + u, 2^{c n s} + \ell + m) > f(2^{c n s} + \ell + m)$ for large $n$. Note that $1+t+u$ does not depend on the function $f$.