156
$\begingroup$

The busy beaver function $\text{BB}(n)$ describes the maximum number of steps that an $n$-state Turing machine can execute before it halts (assuming it halts at all). It is not a computable function because computing it allows you to solve the halting problem.

Are functions like $\text{BB}(n) \bmod 2$, or more generally $\text{BB}(n) \bmod m$ for a modulus $m$, computable? Computing these functions doesn't solve the halting problem, so the above argument doesn't apply.

$\endgroup$
  • 13
    $\begingroup$ This seems like it might well depend sensitively on the details of your machine setup. $\endgroup$ – Chris Eagle Jan 7 '13 at 0:01
  • 10
    $\begingroup$ Some discussion on this question: scottaaronson.com/blog/?p=46 $\endgroup$ – Dan Brumleve Jan 7 '13 at 0:44
  • 5
    $\begingroup$ A variation: can it be shown that $\text{BB}(n)$ is composite infinitely often? This version is seemingly less sensitive to the encoding. $\endgroup$ – Dan Brumleve Jan 7 '13 at 4:02
  • 4
    $\begingroup$ 1-D BB Turing machines are hard to visualize, so I made a page for 2-D Turing Machine BBs.. Once a 1-D Turing machine becomes predictable, it can be classified as halting or infinite. Thus, the point of predictability is the important point. This rarely happens elegantly. The champions tend to be machines that can be extended forward as they get into temporary predictable behaviors. $\endgroup$ – Ed Pegg Feb 26 '13 at 15:51
  • 7
    $\begingroup$ Related. $\endgroup$ – Andrés E. Caicedo Jul 23 '13 at 16:21
7
$\begingroup$

Define $\text{BB}(n)$ as the largest natural number whose Kolmogorov complexity (in a prefix-free binary language) is less than or equal to $n$ bits.

Consider $\text{BB}(n) \space \text{mod} \space 4^n$. This number has a Kolmogorov complexity less than $n + o(n)$, since it can be computed from $\text{BB}(n)$, and $K(\text{BB}(n)) \le n$.

Also consider $\lfloor \Omega \cdot 4^n \rfloor$ where $\Omega$ is Chaitin's constant. This number's Kolmogorov complexity is at least $2 \cdot n - o(n)$ bits (by definition of algorithmic randomness).

So,

$\text{BB}(n) \space \text{mod} \space 4^n \stackrel{?}{=} \lfloor \Omega \cdot 4^n \rfloor$

is computable since it is false for all but finitely many $n$.


Given the first $n$ bits of $\Omega$ it is possible to compute not just $\text{BB}(n)$ but all the $\text{BB}(i)$ for $i$ up to $n$. We can use this to turn the above statement sideways and say something about only the lower bits of each busy beaver number:

$K(\sum_{i \le n}{[4^i \cdot (\text{BB}(i) \space \text{mod} \space 4)]}) < n + o(n)$

implying that

$\sum_{i}{\frac{\text{BB}(i) \space \text{mod} \space 4}{4^i}}$

is not algorithmically random, and in particular,

$\Omega \ne \sum_{i}{\frac{\text{BB}(i) \space \text{mod} \space 4}{4^i}}$ .


A couple more observations:

There is a total computable function $\text{CC}:\mathbb{N}\rightarrow\mathbb{N}$ that inverts $\text{BB}$, i.e. $\text{CC}(\text{BB}(n)) = n$ for all $n \in \mathbb{N}$. It works like this: on input $k$, run every TM with $k$ or fewer states for $k$ steps, and return the fewest number of states of any that halted on the last step. For all $k$ there is a $k$-state machine that terminates in exactly $k$ steps, so there will be a smallest one. This implies immediately that Busy Beaver numbers have some computable properties, for example if $f$ is any computable function, then there is another computable function $g$ such that $f(n) = g(\text{BB}(n))$, namely $g(k) = f(\text{CC}(k))$. But also, we can make $f$ and $g$ be the same function: $\text{CC}$ is non-increasing so it has no cycles and at least one fixed point, call the computable function that finds it $\text{CC}^*$. So, $\text{CC}^*(\text{BB}(n)) = \text{CC}^*(n)$. For $\text{CC}^*$ to be non-trivial there need to be at least two fixed points, surely there always are, but if not just redefine $\text{CC}(k) = k$ on some particular $k$ which is not a $\text{BB}$ number.

On the other extreme, I believe there exists a total computable function $g$ such that $\sum{\frac{g(\text{BB}(n))}{2^n}}$ is algorithmically random: $g(k)$ computes the $\text{CC}(k)^{\text{th}}$ bit of $\Omega$ using the assumption that $\text{BB}(\text{CC}(k)) = k$. I think it should work to to count all programs shorter than $\text{CC}(k)$ that terminate in at most $k$ steps (but more care is needed to describe this and prove that it is total).

| cite | improve this answer | |
$\endgroup$

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.