Kolmogorov complexity: Difference between revisions

Revision as of 06:57, 20 January 2025

Revision as of 07:05, 20 January 2025

Line 254:

It is straightforward to compute upper bounds for ''K''(''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 length of the resulting string – concretely, the size of a [[self-extracting archive]] in the given language.

A string ''s'' is compressible by a number ''c'' if it has a description whose length does not exceed |''s''| − ''c'' bits. This is equivalent to saying that {{math|''K''(''s'') ≤ {{abs|''s''|}} − ''c''}}. Otherwise, ''s'' is incompressible by ''c''. A string incompressible by 1 is said to be simply ''incompressible''&nbsp;– by the [[pigeonhole principle]], which applies because every compressed string maps to only one uncompressed string, [[incompressible string]]s must exist, since there are 2^''n'' bit strings of length ''n'', but only 2^''n'' − 1 shorter strings, that is, strings of length less than ''n'', (i.e. with length 0, 1, ..., ''n''&nbsp;−&nbsp;1).<ref group=note>As there are {{nobrmath|1=''N''_''L'' = 2^''L''}} strings of length ''L'', the number of strings of lengths {{nowrapmath|1=''L'' = 0, 1, ..., ''n'' − 1}} is {{nobrmath|''N''₀ + ''N''₁ + ... + ''N''_''n''−1}} = {{nobrmath|2⁰ + 2¹ + ... + 2^''n''−1}}, which is a finite [[geometric series]] with sum {{nobrmath|2⁰ + 2¹ + ... + 2^''n''−1}} = {{nobrmath|1 = 2⁰ × (1 − 2^''n'') / (1 − 2) = 2^''n'' − 1}}</ref>

For the same reason, most strings are complex in the sense that they cannot be significantly compressed&nbsp;– their ''K''(''s'') is not much smaller than |''s''|, the length of ''s'' in bits. To make this precise, fix a value of ''n''. There are 2^''n'' bitstrings of length ''n''. The [[Uniform distribution (discrete)|uniform]] [[probability]] distribution on the space of these bitstrings assigns exactly equal weight 2^−''n'' to each string of length ''n''.

'''Theorem''': With the uniform probability distribution on the space of bitstrings of length ''n'', the probability that a string is incompressible by ''c'' is at least {{math|1 − 2^−''c''+1 + 2^−''n''}}.

To prove the theorem, note that the number of descriptions of length not exceeding ''n'' − ''c'' is given by the geometric series: