For Kolmogorov complexities $\hspace{.02 in}K$ induced by essentially-optimal description languages,
does there exist an integer $c$ such that for all positive integers $n$,
there exists a string $x$ such that $\;\;\; n \: < \: K(x) \: < \: n\hspace{-0.04 in}+\hspace{-0.03 in}c \;\;\;\;$?

Unlike the question I was inspired by, this question's answer is robust against the choice of $\hspace{.02 in}K\hspace{-0.02 in}$, since by definition $L_{\hspace{.03 in}0}$ is an "essentially-optimal description language" if and only if
it is a computable partial function from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^{\hspace{-0.03 in}*}$ to itself such that for all
computable partial functions $L_{\hspace{.02 in}1}$ from $\{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^{\hspace{-0.03 in}*}$ to itself, there exists an
integer $c$ and a computable (total) function $\: f : \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^{\hspace{-0.03 in}*} \to \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^{\hspace{-0.03 in}*} \:$ such that
for all strings $x$, $\;\;\; \operatorname{length}(\hspace{.05 in}f(x)) \: < \: \operatorname{length}(x)+c \;\;\;$ and $\; L_{\hspace{.03 in}0}\hspace{-0.02 in}(\hspace{.05 in}f(x)) = L_{\hspace{.02 in}1}\hspace{-0.02 in}(x) \:\:$.

  • 1
    $\begingroup$ Can you add more details about "essentially-optimal description languages"? One can define the simple (optimal?) language "1" prints 1 and "0" prints 0 and get an induced $K$ that satisfies your condition, but I argue that this is not what you want :-) $\endgroup$ Jan 27, 2015 at 7:54
  • $\begingroup$ I just did so. $\;$ $\endgroup$
    – user6973
    Jan 27, 2015 at 8:09
  • $\begingroup$ Heuristically one would think yes, since there are so many strings whose KC is within a constant of their length.... $\endgroup$
    – usul
    Jan 27, 2015 at 15:12

1 Answer 1


Suppose $L_0$ is an essentially-optimal description language, and consider the identity function, which is a computable partial function from $\{0,1\}^*$ to itself. According to the definition, there is a computable function $f$ and a constant $C$ such that $|f(x)| \leq |x| + C$ and $L_0(f(x)) = x$.

Take now a Kolmogorov random string $x$ of length $n$. On the one hand, $K(x) \geq n$. On the other hand, we have seen above that $K(x) \leq n + C$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.