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
scroll top