Content deleted Content added
m Automated conversion |
m the randomness of strings |
||
Line 15:
It is however straightforward to compute upper bounds for ''I''(''s''): simply [[compression|compress]] the string ''s'' with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the resulting string's length.
The next important result is about the [[randomness]] of strings. Most strings are complex in the sense that they cannot be significantly compressed: ''I''(''s'') is not much smaller than |''s''|, the length of ''s'' in bits. The precise statement is as follows: there is a constant ''K'' (which depends only on the particular specification of "program" used in the definition of complexity) such that for every ''n'', the [[probability]] that a random string ''s'' has complexity less than |''s''| - ''n'' is smaller than ''K'' 2<sup>-''n''</sup>. 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.''
| |||