# Range of values for Kolmogorov complexity

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?

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$$.
• So for each Kolmogorov complexity value you want to achieve, you need to build a new program interpreter that achieves it for some binary string of length $n$. – JtailHyper Apr 17 '19 at 22:12
• In your example, you say that we can find a length $n-1$ string $w$ such that $K_{L'}(w) = n$. I understand this, you're simply using the fact that there is at least one incompressible string for each $n$, and the rest follows from your definition of $L'$. But I don't quite see how your construction of $L'$ hits every Kolmogorov complexity between $1$ and $n$ for some length $n$ binary string. Could you explain this a little more? Sorry if my question seems dumb, I have almost no intuition for Kolmogorov complexity. – JtailHyper Apr 17 '19 at 22:34
• The definition of $L'$ doesn't depend on $n$. – Yuval Filmus Apr 17 '19 at 22:35