Search code examples
computation-theory

Kolmogorov complexity

I'll be more than thankful if anyone would be able to explain me how Kolmogorov complexity is related to randomness, and random inputs.

Another thing that I can't understand - we know that calculating Kolmogorov complexity of a given input X isn't decidable. Given that, how can it be a measure of randomness?

thanks

Solution

  • Kolmogorov random is a particular definition of the vague intuitive concept of 'random' - which other definition are you referring to when asking for relationship (for reference http://en.wikipedia.org/wiki/Random_number)?

    I don't follow your thought pattern in asking why one would have to be able to determine in the general case which strings are Kolmogorov random in order for the concept to be well-defined. Could you elaborate on what is giving you trouble? If nothing else, allow me to point you to the halting problem - certainly the concept of a program halting is well-defined even though there can be no algorithm for determining, in the general case, whether a particular program exhibits the property.