Is there an infinite set of strings whose Kolmogorov complexities are computable?

Question

Is there an infinite set of strings whose Kolmogorov complexities are computable?

Answer 1

I think you are asking this: is there an infinite r.e. set of pairs $(\sigma,n)$ where $\sigma \in 2^{<\omega}$ is a string of Kolmogorov complexity $n$. The answer to that is no.

For a contradiction, assume such a list is r.e. - then there arbitrarily long strings in it, and thus strings of arbitrarily high Kolmogorov complexity. Define a function $P$ that takes input $\tau \in 2^{<\omega}$ and does the following. First, it effectively enumerates that list until it finds a pair $(\sigma, n)$ where $n > |\tau|$. Then it prints out $\sigma$.

The assumptions we have made ensure that $P$ is a total computable function. Therefore, applying Kleene's recursion theorem to $P$ gives a program $e_0$ that, when run with no input, computes $P(e_0)$. Thus the output of program $e_0$, run with no input, is a string of Kolmogorov complexity larger than $|e_0|$, which is impossible.