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 ifit 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 allcomputable 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 aninteger $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 thatfor 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) \:\:$.
Is Kolmogorov complexity quasi-surjective?
kolmogorov complexity
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$.