Editing Kolmogorov complexity (section)

===Uncomputability of Kolmogorov complexity===

==== A naive attempt at a program to compute ''K'' ====

At first glance it might seem trivial to write a program which can compute ''K''(''s'') for any ''s'', such as the following:

 '''function''' KolmogorovComplexity('''string''' s)
     '''for''' i = 1 '''to''' infinity:
         '''for each''' string p '''of''' length exactly i
             '''if''' isValidProgram(p) '''and''' evaluate(p) == s
                 '''return''' i

This program iterates through all possible programs (by iterating through all possible strings and only considering those which are valid programs), starting with the shortest. Each program is executed to find the result produced by that program, comparing it to the input ''s''. If the result matches then the length of the program is returned.

However this will not work because some of the programs ''p'' tested will not terminate, e.g. if they contain infinite loops. There is no way to avoid all of these programs by testing them in some way before executing them due to the non-computability of the [[halting problem]].

What is more, no program at all can compute the function ''K'', be it ever so sophisticated. This is proven in the following.

==== Formal proof of uncomputability of ''K''====

'''Theorem''': There exist strings of arbitrarily large Kolmogorov complexity. Formally: for each natural number ''n'', there is a string ''s'' with ''K''(''s'') ≥ ''n''.<ref group="note">However, an ''s'' with ''K''(''s'') = ''n'' need not exist for every ''n''. For example, if ''n'' is not a multiple of 7, no [[ASCII]] program can have a length of exactly ''n'' bits.</ref>

'''Proof:''' Otherwise all of the infinitely many possible finite strings could be generated by the finitely many<ref group="note">There are 1 + 2 + 2<sup>2</sup> + 2<sup>3</sup> + ... + 2<sup>''n''</sup> = 2<sup>''n''+1</sup> − 1 different program texts of length up to ''n'' bits; cf. [[geometric series]]. If program lengths are to be multiples of 7 bits, even fewer program texts exist.</ref> programs with a complexity below ''n'' bits.

'''Theorem''':  ''K'' is not a [[computable function]]. In other words, there is no program which takes any string ''s'' as input and produces the integer ''K''(''s'') as output.

The following [[proof by contradiction|'''proof''' by contradiction]] uses a simple [[Pascal (programming language)|Pascal]]-like language to denote programs; for sake of proof simplicity assume its description (i.e. an [[interpreter (computing)|interpreter]]) to have a length of {{val|1400000}} bits.
Assume for contradiction there is a program

 '''function''' KolmogorovComplexity('''string''' s)

which takes as input a string ''s'' and returns ''K''(''s''). All programs are of finite length so, for sake of proof simplicity, assume it to be {{val|7000000000}} bits.
Now, consider the following program of length {{val|1288}} bits:

 '''function''' GenerateComplexString()
     '''for''' i = 1 '''to''' infinity:
         '''for each''' string s '''of''' length exactly i
             '''if''' KolmogorovComplexity(s) ≥ 8000000000
                 '''return''' s

Using <code>KolmogorovComplexity</code> as a subroutine, the program tries every string, starting with the shortest, until it returns a string with Kolmogorov complexity at least {{val|8000000000}} bits,<ref group="note">By the previous theorem, such a string exists, hence the <code>for</code> loop will eventually terminate.</ref> i.e. a string that cannot be produced by any program shorter than {{val|8000000000}} bits. However, the overall length of the above program that produced ''s'' is only {{val|7001401288}} bits,<ref group=note>including the language interpreter and the subroutine code for <code>KolmogorovComplexity</code></ref> which is a contradiction. (If the code of <code>KolmogorovComplexity</code> is shorter, the contradiction remains. If it is longer, the constant used in <code>GenerateComplexString</code> can always be changed appropriately.)<ref group=note>If <code>KolmogorovComplexity</code> has length ''n'' bits, the constant ''m'' used in <code>GenerateComplexString</code> needs to be adapted to satisfy {{nowrap|''n'' + {{val|1400000}} + {{val|1218}} + 7·log<sub>10</sub>(''m'') < ''m''}}, which is always possible since ''m'' grows faster than log<sub>10</sub>(''m'').</ref>

The above proof uses a contradiction similar to that of the [[Berry paradox]]: "<sub>{{color|#8080ff|1}}</sub>The <sub>{{color|#8080ff|2}}</sub>smallest <sub>{{color|#8080ff|3}}</sub>positive <sub>{{color|#8080ff|4}}</sub>integer <sub>{{color|#8080ff|5}}</sub>that <sub>{{color|#8080ff|6}}</sub>cannot <sub>{{color|#8080ff|7}}</sub>be <sub>{{color|#8080ff|8}}</sub>defined <sub>{{color|#8080ff|9}}</sub>in <sub>{{color|#8080ff|10}}</sub>fewer <sub>{{color|#8080ff|11}}</sub>than <sub>{{color|#8080ff|12}}</sub>twenty <sub>{{color|#8080ff|13}}</sub>English <sub>{{color|#8080ff|14}}</sub>words". It is also possible to show the non-computability of ''K'' by reduction from the non-computability of the halting problem ''H'', since ''K'' and ''H'' are [[turing degree#Turing equivalence|Turing-equivalent]].<ref>Stated without proof in: {{cite web |url=http://www.daimi.au.dk/~bromille/DC05/Kolmogorov.pdf |title=Course notes for Data Compression - Kolmogorov complexity |archive-url=https://web.archive.org/web/20090909132048/http://www.daimi.au.dk/~bromille/DC05/Kolmogorov.pdf |archive-date=2009-09-09 |year=2005 |author=P. B. Miltersen |page=7 | url-status=dead}}</ref>

There is a corollary, humorously called the "[[full employment theorem]]" in the programming language community, stating that there is no perfect size-optimizing compiler.