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

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

• I re-tagged away from "complexity-theory" because that tag sounds like computational complexity, or at least could be easily confused with it. Dec 3, 2010 at 2:59
• The phrasing of the question is somewhat imprecise. For any particular string, its Kolmogorov complexity is trivially computable, because the complexity is just some particular natural number. In my answer I took the most reasonable non-trivial interpretation. Dec 3, 2010 at 3:04
• @Carl: thanks for that, I conflated those... Dec 3, 2010 at 5:41
• @CarlMummert 'For any particular string, its Kolmogorov complexity is trivially computable, because the complexity is just some particular natural number.' Does this mean that there exist strings with known Kolmogorov complexity?
– user93511
Jun 14, 2016 at 13:15
• @Aidan Rocke: well, whatever the Kolmogorov complexity of $\langle 0101 \rangle$ is, that is its complexity, which we can hard-code into a program. The issue with computation is when we want a program that can take arbitrary strings as inputs, not just one particular string. Separately, in some universal prefix free codes we do know the complexity of particular strings. For example we can arrange any particular string we want, $s$, to have complexity $1$ by setting up the universal prefix free code $\phi$ so that $\phi(\langle 0\rangle) = s$. That still leaves all strings of form $1\sigma$ Jun 14, 2016 at 13:44

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.
• @Ross Millikan: The problem is that the $\log(n)$ type bound is just an upper bound on the complexity. The question asks for an infinite set on which we can compute the complexity exactly, not just provide an upper bound. An exact computation like that is impossible, which is what my answer is intended to prove. Dec 9, 2010 at 15:48