4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ For any computable function $f$, there is some $N$ such that for all $n>N$, $BB(n)>f(n)$. $\endgroup$ – f'' Jul 12 '16 at 3:28
  • $\begingroup$ 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)$. $\endgroup$ – Matt Samuel Jul 12 '16 at 3:29
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – f'' Jul 12 '16 at 3:31
  • 1
    $\begingroup$ @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". $\endgroup$ – 6005 Jul 12 '16 at 3:33
  • $\begingroup$ @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$. $\endgroup$ – 6005 Jul 12 '16 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.