Kolmogorov complexity: Difference between revisions

Revision as of 08:38, 11 June 2003

Revision as of 16:39, 23 October 2003

Line 9:

In the following, we will fix one definition and simply write ''I''(''s'') for the complexity of the string ''s''.

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 lessfewer than twenty English words. Well, I just defined it in lessfewer 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.