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

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?

• For any computable function $f$, there is some $N$ such that for all $n>N$, $BB(n)>f(n)$. – f'' Jul 12 '16 at 3:28
• I don't know in what sense it is meant, but there is an obvious interpretation that makes perfect sense: given a computable function $f$ on the positive integers and any integer constant $C$ there is an $N$ such that for all $n>N$ we have that $Cf(n)<BB(n)$, I.e. $f=o(BB)$. – Matt Samuel Jul 12 '16 at 3:29

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.

• Aren't these propositions equivalent? If there was some computable $f$ such that $\lim_{n \to \infty} \frac{BB(n)}{f(n)} = x$ for some finite $x$, then $g(n)=Cf(n)$ for some $C>x$ would also be computable and violate proposition 1. – f'' Jul 12 '16 at 3:31
• @f'' True :) But they're on the face of it different -- in particular, if you remove the quantification ("for any computable function") they are not equivalent, so I wanted to distinguish those two senses of "grows faster than". – 6005 Jul 12 '16 at 3:33
• @f'' By the way, the opposite of Proposition 2 would not be that, but rather $\liminf_{n \to \infty} \frac{BB(n)}{f(n)} = x < \infty$. – 6005 Jul 12 '16 at 3:34