By what measure does the busy beaver function grow faster than any computable function?

Question

It has been proven that the busy beaver function grows faster than any computable function. But I wouldn't think that speed of growth is well-defined. What is the definition? Is there some index?

Answer 1

It's a good question. Let's say $BB(n)$ denotes the busy beaver function of a positive integer $n$. Of course, you can always define a computable function that is bigger than $BB(n)$ for small $n$. For example, here's a computable function: $$ f(n) = BB(10000). $$ It's computable because it just returns a specific number, and it's bigger than $BB(n)$ for $1 \le n \le 9999$.

So when we say $BB(n)$ grows faster than any computable function, we must mean something for large enough $n$. One way of saying it is this:

Proposition 1. For any computable function $f$, there is a positive integer $N$ such that for all $n > N$, $BB(n) > f(n)$.

In other words, once you go out far enough (past the integer $N$), busy beaver beats $f(n)$.

A stronger thing to say (and more in line with what "grows faster" usually means in math, actually) is the following statement, also true:

Proposition 2. For any computable function $f$, $\lim_{n \to \infty} \frac{BB(n)}{f(n)} = \infty$.

If you're not familiar with limits, it's saying that eventually, $BB(n)$ will be at least $100$ times as large as $f(n)$; if you go even further it will be at least $1000$ times as large, and so on; for any constant number $C$, it will eventually be that $BB(n)$ is $C$ times or bigger than $f(n)$.

In practice, "eventually" here is a gross understatement: the busy beaver function will become astronomically larger (i.e., not just $10$ or $100$ times larger) than most of the usual computable functions you can think of very quickly, probably after $n = 5$ or so.