Kolmogorov complexity: Difference between revisions

Revision as of 22:23, 23 September 2004

Revision as of 22:25, 23 September 2004

Line 21:

The next important result is about the [[randomness]] of strings. Most strings are complex in the sense that they cannot be significantly compressed: ''K''(''s'') is not much smaller than |''s''|, the length of ''s'' in bits. The precise statement is as follows:

the [[probability]] that a random string of length ''n'' has complexity less than ''n''- − ''k'' is smaller than 2^{-−''k''}. The proof is a [[counting argument]]: you count the programs and the strings, and compare. This theorem is the justification for Mike Goldman's challenge in the [http://www.faqs.org/faqs/compression-faq/ comp.compression FAQ]:

:''I will attach a prize of $5,000 to anyone who successfully meets this challenge. First, the contestant will tell me HOW LONG of a data file to generate. Second, I will generate the data file, and send it to the contestant. Last, the contestant will send me a decompressor and a compressed file, which will together total in size less than the original data file, and which will be able to restore the compressed file to the original state.''