3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – JtailHyper Apr 17 at 22:12
  • $\begingroup$ Not quite. You're looking for a single program interpreter with a certain range of Kolmogorov complexities. $\endgroup$ – Yuval Filmus Apr 17 at 22:13
  • $\begingroup$ 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. $\endgroup$ – JtailHyper Apr 17 at 22:34
  • $\begingroup$ The definition of $L'$ doesn't depend on $n$. $\endgroup$ – Yuval Filmus Apr 17 at 22:35
  • $\begingroup$ Thank you, I think I got it. $\endgroup$ – JtailHyper Apr 17 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.