Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
I re-tagged away from "complexity-theory" because that tag sounds like computational complexity, or at least could be easily confused with it. –  Carl Mummert Dec 3 '10 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. –  Carl Mummert Dec 3 '10 at 3:04
    
@Carl: thanks for that, I conflated those... –  J. M. Dec 3 '10 at 5:41

1 Answer 1

up vote 11 down vote accepted

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.

share|improve this answer
    
Thank you, I understand why my question was ambiguous now. –  user4353 Dec 3 '10 at 6:26
    
I was worried about the strings being too regular. For example, let each string be all 1's. I guess your point is that an n-bit string of all 1's still has complexity log(n) which grows arbitrarily. Is that right? Thanks –  Ross Millikan Dec 8 '10 at 0:58
    
@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. –  Carl Mummert Dec 9 '10 at 15:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.