Busy Beavers are (allmost) incompressible

After a long time, here we are again … let’s resume with a small (and rather trivial) post …

Busy Beavers are allmost incompressible! … easy fact, but I didn’t find it anywhere.

Let $\sigma(M)$ be the number of $1$s left on the tape after the excution of the Turing machine $M$ (the tape is initially blank). A Turing machine $M$ of length $n$ is a Busy Beaver if, for all Turing machines $M’$ of length $n$, we have $\sigma(M’) \leq \sigma(M)$; and we define the busy-beaver function $\Sigma: \mathbb{N} \to \mathbb{N} $ as $\Sigma(n) = \sigma(M)$. Note that our definition of “Busy Beaver” is slightly different from the standard one: we consider the length of the Turing machines in a fixed reasonable encoding scheme, not the number of states.

Suppose that a Turing machine $B$ of length $n$ is a Busy Beaver. If $p$ is the smallest Turing machine that outputs a representation of $B$ when executed on a blank tape ($U(p) = B$) we can build a Turing machine $p’$ that extends the behaviour of $p$ in this way:

  • mirror the execution of $p$ until it halts;
  • then simulate the execution of the Turing machine represented by the output of $p$ until it halts (i.e. it simulates the execution of $B$);
  • and finally find a $0$, overwrite it with a $1$ and halt.

In the simulation of $B$ we can make a one-to-one correspondence between the $i$-th simulated cell $T^B[i]$ and a group of $k$ cells of the actual tape $T[i_1,..,i_k]$ of $p’$ in such a way that if cell $T^B[i] =  1$ during a simulation step, then at least one of $T[i_1],..,T[i_k]$ is $1$.

Hence, by construction, at the end of the whole execution of $p’$, the number of $1$ on the tape is greater than those left on the tape by $B$: $\sigma(p’) > \sigma(B) = \Sigma(n)$.

So we must have $|p’| > n$, but $|p’| = |p| + c = C(B) + c’$ where $C(B)$ is the Kolmogorov complexity of $B$; and finally:

$$C(B) > n – c’$$

where $c’$ doesn’t depend on $n$ but only on the computational model.

 

2 thoughts on “Busy Beavers are (allmost) incompressible

  1. I don’t know much about this, but the idea is that you can only compress a busy beaver by a constant factor c’. Correct?

  2. To be pedantic, $c’$ is not a “factor”; it is a costant (small with respect to an arbitrarily large $n$) that depends only on the computational model. Informally, if $|B| = n$ (no matter how big is $n$), the smallest program that “prints” $B$ cannot be shorter than $n-c’$.

Leave a Reply

Your email address will not be published. Required fields are marked *