# Busy Beaver function growth rate compared to computable functions

Fix a definition of a turing machine (or a programming language) and define $BB(n)$ to be the maximum of number of steps a program with less than $n$ states (or with less than $n$ bits) can take to halt. In particular, we ignore programs that don't halt.

There is a standard, easy proof that for any computable function $f(n)$, there exists a $n$ for which $BB(n) > f(n)$. If this were false, then we could solve the halting problem by simulating a given machine $M$ with $n$ states for up to $BB(n)$ steps and if it hasn't halted by then, we know that it will never halt.

However, I have seen it stated sometimes that $BB(n)$ grows faster than $f(n)$ in the stronger sense that for all $n \geq N$, ($N$ a large number depending on $f$) $BB(n) > f(n)$.

How is this proved? For instance, I don't see how to rule out the case that $BB(n) < f(n)$ for all $n$ except one particular value but this one particular value turns out to be uncomputable.

• Re: your last sentence, no particular natural number can be "uncomputable", but it is true that there may be no way to uniformly compute this value $n$ from an index for $f$. Jun 3, 2021 at 7:33
• More or less identical question here with answers of its own. Jun 9 at 18:13

This is actually a bit messy.

First, here's a sketch of the proof of the claim:

Fix an increasing total computable function $f$. There is a natural way to effectively produce, given $k\in\mathbb{N}$, a Turing machine $M_k$ which on a blank tape first computes $f(k)$ and then dithers around for that many steps and then halts. By examining this construction, we can see that the number of states of $M_k$ is bounded by $C_f+k$ for some constant $C_f$. This tells us that:

For every increasing total computable $f$ there is some constant $C_f$ such that $BB(C_f+n)\ge f(n)$ for all $n$.

Now we make the following definition:

For an increasing total computable function $f$, let $g_f: x\mapsto f(2x)$.

It's easy to see that since $BB(C_{g_f}+n)\ge g(n)$ for all $n$ and some constant $C_{g_f}$, we must have $BB$ eventually dominate $f$: $\color{red}{\mbox{if$m\ge C_{g_f}$}}$ then $$BB(C_{g_f}+m)\ge g(m)=f(2m)\color{red}{\ge} f(C_{g_f}+m),$$ and so $BB(x)\ge f(x)$ for all $x\ge C_{g_f}$.

Now, note that in the above we didn't just use general arguments about computability; we actually talked about building Turing machines (and bullsh!tted a bit - "by examining this construction, we can see" ...). It turns out there's a good reason for this: the statement is not true for "coarse" reasons. The rest of this answer discusses this situation.

Let me begin by considering a variant of the busy beaver, the "Workaholic Wombat:"

$WW(n)=\max\{t:$ for some Turing machine $M$ with $<n$ states and some $k<n$, $M$ halts after exactly $t$ steps on input $k\}.$

Note the new ingredient: we're allowing inputs as well as machines. WW and BB are Turing equivalent, of course, the crucial point being that the inputs allowed for $WW(n)$ are bounded by $n$. However, $WW(n)$ has much better behaved asymptotics:

For every computable total $f$, $WW$ dominates $f$.

Proof. Fix $f$ total computable. Let $M$ be the Turing machine which on input $k$ computes $f(k+1)$, dithers around for $f(k)$-many steps, and then halts. Suppose $M$ has $n$ states; then for each $m\ge n$ we have $WW(m+1)>f(m+1)$. $\quad\Box$

This is an example of a coarse argument: it doesn't depend on the fine details of exacly how we represent Turing machines. This argument holds for any "reasonable enumeration" (or "finite-to-one enumeration" - multiple Turing machines may have the same number of states, but there are only finitely many with a given number of states) of Turing machines. However, there are plenty of results which are more finicky. My favorite example is the Padding Lemma. This obviously-true fact turns out to be dependent on the way we list Turing machines:

There is an effective enumeration of partial computable functions such that every partial computable function occurs exactly once on the list.

Such an enumeration is called a Friedberg enumeration. In the statement above, we have to be very careful what we mean by "effective enumeration of partial computable functions," and thinking about this issue will eventually lead you to the notion of an "admissible numbering" which rules out this sort of nonsense. There are other sillinesses which effective enumerations of partial computable functions can display, and it can be fun to play around with them.

Now, any effective way of listing partial computable functions gives rise to a corresponding Busy Beaver function and a corresponding Workaholic Wombat function. As observed above, the WW will still dominate every total computable function; however, it's not hard to cook up listings whose BBs do not dominate every total computable function. The conclusion is:

Proving that BB dominates every total computable function is going to take some playing around with the precise details of Turing machines, and can't just be done via general "coarse" considerations.

• Excellent answer, just what I was looking for! I have no idea how after a year and a half this has only gathered one upvote (now two!). Jan 26, 2020 at 13:20
• I suppose for every monotonically non-decreasing computable function $f(n)$ it holds that $BB(c + BB^{-1}(n))\ge f(n)$, where $c$ is the minimum amount of states a TM that computes $f(n)$ has to have. Which also makes sense, because if it was $BB(c + g(n))$ where $g(n)$ is some computable function, then $BB(n)$ would be computable as well, so $g(n)$ has to grow slower than every increasing computable function (but it has to be growing). Jun 5 at 11:31
• Could you have a look at this answer of mine to a near-identical question? I think it proves that the Radó argument works as soon as the s-m-n theorem holds (for the chosen enumeration) with a primitive recursive substitution function. Curiously, according to sources, the s-m-n theorem is stated with different conditions on this substitution function, some authors say “primitive recursive”, some only “computable”. Jun 9 at 19:34

If it would indeed be the case that $BB(n) < f(n)$ for all $n$ except one particular value $n_0$, then the Busy Beaver function becomes computable, because we know that $BB(n) < BB(n+1)$ for all $n$, and so $BB(n_0) < BB(n_0+1) < f(n_0+1)$, and of course for all other $n$: $BB(n) < f(n)$, and so we have that $BB(n) < max(f(n), f(n+1))$ for all $n$, and thus we would have a computable function, namely $max(f(n), f(n_1))$, that gives a computable upperbound ... which the Busy Beaver function does not have.

• Very nice but I don't think this quite proves the theorem that for all large $n$, $BB(n) > f(n)$. What if there were infinitely many exceptions? Or some other obstruction? Apr 15, 2018 at 17:43
• @ArithmeticGeometer You're quite right! Hmm ... Apr 15, 2018 at 18:20

The basic argument seems to show that there is no total recursive function $f:\mathbb{N} \rightarrow \mathbb{N}$ that eventually dominates the function $bb:\mathbb{N} \rightarrow \mathbb{N}$. That is, the basic argument seems to show that $bb(n)>f(n)$ for infinitely many values of $n$.

If we want to show that $bb$ eventually dominates every total recursive function $f$, then it seems a bit more work is needed. More precisely, we want to show that for every total recursive function $f$, there exists a value $N$ so that for all $n\ge N$ we have $bb(n)>f(n)$. It seems that this should be true under fairly reasonable assumptions.

However, before that, you wrote in the last paragraph of your question: "For instance, I don't see how to rule out the case that $BB(n) < f(n)$ for all $n$ except one particular value but this one particular value turns out to be uncomputable." Unless I misunderstood this, this is ruled out because of very basic reasons. That is, suppose that for value $a$ we have $BB(a) \ge f(a)$. Just modify the given (supposedly) computable function $f$ to form a (supposedly) computable function $g$ so that $g(x)=f(x)$ when $x\neq a$ ..... and furthermore $g(a)=BB(a)$. Now we can use the usual basic argument to show that $g$ is not computable, and hence arrive at a contradiction.

Now coming back to the original question of showing that $bb$ eventually dominates every total recursive function $f$ (sorry if this is just a repeat of the other answers). Consider a reasonable enumeration of programs (of one input variable) so that a program with a smaller size has always smaller index than a program with larger size (for the sake of easier visualisation). Define a function $h:\mathbb{N} \rightarrow \mathbb{N}$ with the following equation(for all $n$): $h(n)=bb(2n)$. Now it can be shown that $h$ eventually dominates every total recursive function under the following assumptions/observations:

(1) If we assume that the variables in our program can only be incremented by $1$ at most (in one command), then we can observe that we can re-write a program $P1$ of length $N$ (when given an input $a$) as a program $P2$ of length $a+N$ (by placing increment commands for input variable at the beginning). The important point is that the output of $P1$ on input $a$ will be the same as output of $P2$ on input $0$.

(2) We further assume that we count the time in such a manner so that the time is incremented at least by $1$ on "every" command. And further every variable (except the input variable) starts with value $0$. With these further assumptions it is easy to see that if a program $P$ of length $N$ computes an arbitrary total recursive function $f$, then $f(n) \le bb(n+N)$ for all values $n$.

Now for any value $n \ge N$, we have: $f(n) \le bb(n+N) \le bb(n+n)=bb(2n)=h(n)$. This completes the first part of the proof I think. But this doesn't prove that $bb$ eventually dominates every total recursive function $f$. It only shows that $h(n)=bb(2n)$ eventually dominates every total recursive function $f$.

EDIT: My previous argument regarding $bb$ eventually dominating every recursive function was too vague. Here is a clearer explanation. Define a function $stair:\mathbb{N} \rightarrow \mathbb{N}$ so that: $stair(n)=bb(n)$ when $n$ is even and further $stair(n)=bb(n-1)$ when $n$ is odd.

Now it can be shown without difficulty that the function $stair$ eventually dominates every total recursive function. By contradiction, assume that there was a computable function $f$ that was greater than $stair(n)$ for infinitely many values of $n$. Then we can define a computable function $g$ so that:
$g(n)=max(f(2n),f(2n+1))$

But now the function $g(n)$ must be greater than $bb(2n)=h(n)$ for infinitely many values. Since this can't be true, our original assumption is incorrect.

Also it is clear that $bb(n) \ge stair(n)$ for all $n$. Hence $bb$ also eventually dominates every total recursive function. END

With a machine-based computational model, it seems to me that a few specific details perhaps may have to be changed. But I guess the basic ideas should remain the same.