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.