Range of values for Kolmogorov complexity

Question

Let $n$ be a positive integer. Is it true that for all $1\leq i \leq n$ there exists a length $n$ binary string $w$ such that $K(w) = i$. Where $K(w)$ is the Kolmogorov complexity of $w$.

For each $i$ there are clearly $2^i$ programs of that length. But can we be sure at least one of them (when executed) generate a length $n$ binary string?

Answer 1

The answer depends on the exact choice of program description language. We can define Kolmogorov complexity with respect to any admissible program description language. A program description language $L$ is admissible if for all program description languages $L'$, we have $K_L(x) \leq K_{L'}(x) + C_{L'}$, for some constant $C_{L'}$ depending only on $L'$.

We start by showing how to construct an admissible program description language in which all Kolmogorov complexities are even. Let $L$ be an admissible program description language. We define a new program description language $L'$ as follows: if $|x|$ is odd or $x = \epsilon$ then $L'(x) = \epsilon$; if $|x|$ is even and $x=0y$ then $L'(x) = L(y)$; and if $|x|$ is even and $x=1y$ then $L'(x) = L(z)$, where $z$ is obtained from $y$ by removing the last symbol. Since $K_{L'}(x) \leq K_L(x) + 2$, $L'$ is admissible. On the other hand, it is easy to check that $K_{L'}$ is always even.

Conversely, we can also arrange that all Kolmogorov complexities would be achieved. Let $L$ be an admissible program description language. We construct a new admissible program description language $L'$ as follows: $L'(\epsilon) = z$, where $z$ is some string satisfying $K_L(z) < |z|$ (we can choose $z = 0^{2^n}$ for large enough $n$); $L'(0x) = x$; and $L'(1x) = L(x)$. Then $K_{L'}(z) = 0$, and for $w \neq z$, we have $K_{L'}(w) = \min(|w|,K_L(w)) + 1$. For every $n \geq 1$, we can find a string $w$ of length $n-1$ such that $K_L(w) \geq n-1$. This string satisfies $K_{L'}(w) = n$.