What properties of busy beaver numbers are computable?

Solution 1:

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).