Content deleted Content added
'''Kolmogorov complexity''' |
Andre Engels (talk | contribs) mNo edit summary |
||
Line 13:
The first surprising result is that ''I''(''s'') cannot be computed: there is no general [[algorithm]] which takes a string ''s'' as input and produces the number ''I''(''s'') as output. The proof is a formalization of the amusing [[Berry paradox]]: "Let ''n'' be the smallest number that cannot be defined in less than twenty English words. Well, I just defined it in less than twenty English words."
It is however straightforward to compute upper bounds for ''I''(''s''): simply [[data 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]:
| |||