Busy Beaver function growth rate compared to computable functions

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.