Kolmogorov complexity

Question

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

Answer 1

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.

Answer 2

You should think the other way round. If something is not random, it means it follows some law, and this law can give a simpler description of the information. Think of zip: instead of the file you give a procedure to generate the file that is usually more compact than the source file. This is possible because the source file contained some order: if the source file was a random sequence of characters no compression would have been possible.

If you are interested in this topic, I strongly recommend "Computability and Randomness" by Andre' Nies, Oxford Logic Guides n.51.