Range of values for Kolmogorov complexity
-
05-11-2019 - |
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?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange