# Difference between revisions of "Kolmogorov complexity"

en>Gracefool m (emphasis) |
en>Jochen Burghardt (→References: removed redundant ref.s appearing also as footnote 1,2) |
||

Line 1: | Line 1: | ||

− | |||

− | |||

− | Kolmogorov complexity is | + | {| style="float:right" |

+ | | [[Image:Mandelpart2 red.png|300px|right|thumb|This image illustrates part of the [[Mandelbrot set]] [[fractal]]. Simply storing the 24-bit color of each pixel in this image would require 1.62 million bits, but a small computer program can reproduce these 1.62 million bits using the definition of the Mandelbrot set and the coordinates of the corners of the image. Thus, the Kolmogorov complexity of the raw file encoding this bitmap is much less than 1.62 million.]] | ||

+ | |} | ||

+ | {{distinguish|descriptive complexity theory}} | ||

+ | In [[algorithmic information theory]] (a subfield of [[computer science]] and [[mathematics]]), the '''Kolmogorov complexity''' (also known as '''descriptive complexity''', '''Kolmogorov–[[Gregory Chaitin|Chaitin]] complexity''', '''algorithmic entropy''', or '''program-size complexity''') of an object, such as a piece of text, is a measure of the [[computability]] resources needed to specify the object. It is named after [[Andrey Kolmogorov]], who first published on the subject in 1963.<ref>{{cite journal|authorlink=Andrey Kolmogorov|first=Andrey|last=Kolmogorov|year=1963|title=On Tables of Random Numbers| journal=[[Sankhya (journal)|Sankhyā]] Ser. A.|volume=25|pages=369–375|mr=178484}}</ref><ref>{{cite journal|authorlink=Andrey Kolmogorov|first=Andrey|last=Kolmogorov|year=1998|title=On Tables of Random Numbers| journal=Theoretical Computer Science|volume=207|issue=2|pages=387–395|doi=10.1016/S0304-3975(98)00075-9 |mr=1643414}}</ref> | ||

− | For example, consider the following two [[string (computer science)|strings]] of | + | For example, consider the following two [[string (computer science)|strings]] of 32 lowercase letters and digits: |

− | <pre> | + | <pre>abababababababababababababababab</pre> |

− | <pre> | + | <pre>4c1j5b2p0cv4w1x8rx2y39umgw5q85s7</pre> |

− | The first string has a short English-language description, namely "ab | + | The first string has a short English-language description, namely "ab 16 times", which consists of '''11''' characters. The second one has no obvious simple description (using the same character set) other than writing down the string itself, which has '''32''' characters. |

− | + | More formally, the [[complexity]] of a string is the length of the shortest possible description of the string in some fixed [[Turing complete|universal]] description language (the sensitivity of complexity relative to the choice of description language is discussed below). It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes larger than the length of the string itself. Strings, like the ''abab'' example above, whose Kolmogorov complexity is small relative to the string's size are not considered to be complex. | |

− | |||

− | More formally, the [[complexity]] of a string is the length of the shortest possible description of the string in some fixed [[Turing complete|universal]] | ||

The notion of the Kolmogorov complexity can be used to state and prove impossibility results akin to [[Gödel's incompleteness theorem]] and [[halting problem|Turing's halting problem]]. | The notion of the Kolmogorov complexity can be used to state and prove impossibility results akin to [[Gödel's incompleteness theorem]] and [[halting problem|Turing's halting problem]]. | ||

==Definition== | ==Definition== | ||

− | + | The Kolmogorov complexity can be defined for any mathematical object, however for simplicity, it will be defined here for strings. We must first specify a description language for strings. Such a description language can be based on any computer programming language, such as [[Lisp programming language|Lisp]], [[Pascal (programming language)|Pascal]], or [[Java virtual machine]] bytecode. If '''P''' is a program which outputs a string ''x'', then '''P''' is a description of ''x''. The length of the description is just the length of '''P''' as a character string, multiplied by the number of bits in a character (e.g. 7 for [[ASCII]]). | |

− | We could, alternatively, choose an encoding for [[Turing machine]]s, where an ''encoding'' is a function which associates to each Turing Machine '''M''' a bitstring <'''M'''>. If '''M''' is a Turing Machine which, on input ''w'', outputs string ''x'', then the concatenated string <'''M'''> ''w'' is a description of ''x''. For theoretical analysis, this approach is more suited for constructing detailed formal proofs and is generally preferred in the research literature | + | We could, alternatively, choose an encoding for [[Turing machine]]s, where an ''encoding'' is a function which associates to each Turing Machine '''M''' a bitstring <'''M'''>. If '''M''' is a Turing Machine which, on input ''w'', outputs string ''x'', then the concatenated string <'''M'''> ''w'' is a description of ''x''. For theoretical analysis, this approach is more suited for constructing detailed formal proofs and is generally preferred in the research literature. In this article, an informal approach is discussed. |

Any string ''s'' has at least one description, namely the program: | Any string ''s'' has at least one description, namely the program: | ||

Line 27: | Line 27: | ||

'''return''' ''s'' | '''return''' ''s'' | ||

− | If a description of ''s'', ''d''(''s''), is of minimal length (i.e. it uses the fewest | + | If a description of ''s'', ''d''(''s''), is of minimal length (i.e. it uses the fewest bits), it is called a '''minimal description''' of ''s''. Thus, the length of ''d''(''s'') (i.e. the number of bits in the description) is the '''Kolmogorov complexity''' of ''s'', written ''K''(''s''). Symbolically, |

− | : | + | :''K''(''s'') = |''d''(''s'')|. |

− | + | The length of the shortest description will depend on the choice of description language; but the effect of changing languages is bounded (a result called the ''invariance theorem''). | |

− | + | ==Invariance theorem== | |

− | : | + | ===Informal treatment=== |

+ | There are some description languages which are optimal, in the following sense: given any description of an object in a description language, I can use that description in my optimal description language with a constant overhead. The constant depends only on the languages involved, not on the description of the object, or the object being described. | ||

− | + | Here is an example of an optimal description language. A description will have two parts: | |

− | : < | + | * The first part describes another description language. |

+ | * The second part is a description of the object in that language. | ||

+ | |||

+ | In more technical terms, the first part of a description is a computer program, with the second part being the input to that computer program which produces the object as output. | ||

+ | |||

+ | '''The invariance theorem follows:''' Given any description language ''L'', the optimal description language is at least as efficient as ''L'', with some constant overhead. | ||

+ | |||

+ | '''Proof:''' Any description ''D'' in ''L'' can be converted into a description in the optimal language by first describing ''L'' as a computer program ''P'' (part 1), and then using the original description ''D'' as input to that program (part 2). The | ||

+ | total length of this new description ''D''’ is (approximately): | ||

+ | |||

+ | :|''D''’| = |''P''| + |''D''| | ||

+ | |||

+ | The length of ''P'' is a constant that doesn't depend on ''D''. So, there is at most a constant overhead, regardless of the object described. Therefore, the optimal language is universal [[up to]] this additive constant. | ||

+ | |||

+ | ===A more formal treatment=== | ||

+ | '''Theorem''': If ''K''<sub>1</sub> and ''K''<sub>2</sub> are the complexity functions relative to [[Turing complete]] description languages ''L''<sub>1</sub> and ''L''<sub>2</sub>, then there is a constant ''c'' – which depends only on the languages ''L''<sub>1</sub> and ''L''<sub>2</sub> chosen – such that | ||

+ | |||

+ | :∀''s''. -''c'' ≤ ''K''<sub>1</sub>(''s'') - ''K''<sub>2</sub>(''s'') ≤ ''c''. | ||

+ | |||

+ | '''Proof''': By symmetry, it suffices to prove that there is some constant ''c'' such that for all strings ''s'' | ||

+ | |||

+ | :''K''<sub>1</sub>(''s'') ≤ ''K''<sub>2</sub>(''s'') + ''c''. | ||

Now, suppose there is a program in the language ''L''<sub>1</sub> which acts as an [[interpreter (computing)|interpreter]] for ''L''<sub>2</sub>: | Now, suppose there is a program in the language ''L''<sub>1</sub> which acts as an [[interpreter (computing)|interpreter]] for ''L''<sub>2</sub>: | ||

Line 47: | Line 69: | ||

where ''p'' is a program in ''L''<sub>2</sub>. The interpreter is characterized by the following property: | where ''p'' is a program in ''L''<sub>2</sub>. The interpreter is characterized by the following property: | ||

− | : Running InterpretLanguage on input ''p'' returns the result of running ''p''. | + | : Running <code>InterpretLanguage</code> on input ''p'' returns the result of running ''p''. |

− | Thus, if '''P''' is a program in ''L''<sub>2</sub> which is a minimal description of ''s'', then InterpretLanguage('''P''') returns the string ''s''. The length of this description of ''s'' is the sum of | + | Thus, if '''P''' is a program in ''L''<sub>2</sub> which is a minimal description of ''s'', then <code>InterpretLanguage</code>('''P''') returns the string ''s''. The length of this description of ''s'' is the sum of |

− | # The length of the program InterpretLanguage, which we can take to be the constant ''c''. | + | # The length of the program <code>InterpretLanguage</code>, which we can take to be the constant ''c''. |

# The length of '''P''' which by definition is ''K''<sub>2</sub>(''s''). | # The length of '''P''' which by definition is ''K''<sub>2</sub>(''s''). | ||

This proves the desired upper bound. | This proves the desired upper bound. | ||

− | |||

− | |||

==History and context== | ==History and context== | ||

Algorithmic information theory is the area of computer science that studies Kolmogorov complexity and other complexity measures on strings (or other [[data structure]]s). | Algorithmic information theory is the area of computer science that studies Kolmogorov complexity and other complexity measures on strings (or other [[data structure]]s). | ||

− | The concept and theory of Kolmogorov Complexity is based on a crucial theorem first discovered by [[Ray Solomonoff]], who published it in 1960, describing it in "A Preliminary Report on a General Theory of Inductive Inference"<ref>{{cite journal |authorlink=Ray Solomonoff | last=Solomonoff |first= Ray | url=http://world.std.com/~rjs/rayfeb60.pdf |format=PDF | title=A Preliminary Report on a General Theory of Inductive Inference | journal= Report V-131 |publisher= Zator Co. |location= Cambridge, Ma. | date= February 4, 1960 }} [http://world.std.com/~rjs/z138.pdf revision], Nov., 1960.</ref> as part of his invention of [[algorithmic probability]]. He gave a more complete description in his 1964 publications, "A Formal Theory of Inductive Inference," Part 1 and Part 2 in ''Information and Control''.<ref>{{cite | + | The concept and theory of Kolmogorov Complexity is based on a crucial theorem first discovered by [[Ray Solomonoff]], who published it in 1960, describing it in "A Preliminary Report on a General Theory of Inductive Inference"<ref>{{cite journal |authorlink=Ray Solomonoff | last=Solomonoff |first= Ray | url=http://world.std.com/~rjs/rayfeb60.pdf |format=PDF | title=A Preliminary Report on a General Theory of Inductive Inference | journal= Report V-131 |publisher= Zator Co. |location= Cambridge, Ma. | date= February 4, 1960 }} [http://world.std.com/~rjs/z138.pdf revision], Nov., 1960.</ref> as part of his invention of [[algorithmic probability]]. He gave a more complete description in his 1964 publications, "A Formal Theory of Inductive Inference," Part 1 and Part 2 in ''Information and Control''.<ref>{{cite doi|10.1016/S0019-9958(64)90223-2}}</ref><ref>{{cite doi|10.1016/S0019-9958(64)90131-7 }}</ref> |

− | Andrey Kolmogorov later [[multiple discovery|independently published]] this theorem in ''Problems Inform. Transmission'',<ref>{{cite journal | volume= 1| issue=1 |year=1965 | pages= 1–7 | title =Three Approaches to the Quantitative Definition of Information | url=http://www.ece.umd.edu/~abarg/ppi/contents/1-65-abstracts.html#1-65.2 | journal = Problems Inform. Transmission | first=A.N. | last= | + | Andrey Kolmogorov later [[multiple discovery|independently published]] this theorem in ''Problems Inform. Transmission'',<ref>{{cite journal | volume= 1| issue=1 |year=1965 | pages= 1–7 | title =Three Approaches to the Quantitative Definition of Information | url=http://www.ece.umd.edu/~abarg/ppi/contents/1-65-abstracts.html#1-65.2 | journal = Problems Inform. Transmission | first=A.N. | last=Kolmogorov }}</ref> Gregory Chaitin also presents this theorem in ''J. ACM'' – Chaitin's paper was submitted October 1966 and revised in December 1968, and cites both Solomonoff's and Kolmogorov's papers.<ref>{{cite doi | 10.1145/321526.321530}}</ref> |

The theorem says that, among algorithms that decode strings from their descriptions (codes), there exists an optimal one. This algorithm, for all strings, allows codes as short as allowed by any other algorithm up to an additive constant that depends on the algorithms, but not on the strings themselves. Solomonoff used this algorithm, and the code lengths it allows, to define a "universal probability" of a string on which inductive inference of the subsequent digits of the string can be based. Kolmogorov used this theorem to define several functions of strings, including complexity, randomness, and information. | The theorem says that, among algorithms that decode strings from their descriptions (codes), there exists an optimal one. This algorithm, for all strings, allows codes as short as allowed by any other algorithm up to an additive constant that depends on the algorithms, but not on the strings themselves. Solomonoff used this algorithm, and the code lengths it allows, to define a "universal probability" of a string on which inductive inference of the subsequent digits of the string can be based. Kolmogorov used this theorem to define several functions of strings, including complexity, randomness, and information. | ||

− | When Kolmogorov became aware of Solomonoff's work, he acknowledged Solomonoff's priority.<ref>{{cite journal | last1=Kolmogorov | first1=A. | title=Logical basis for information theory and probability theory | journal=IEEE Transactions on Information Theory | volume=14|issue=5 | pages=662–664 | year=1968 | doi =10.1109/TIT.1968.1054210 }}</ref> For several years, Solomonoff's work was better known in the Soviet Union than in the Western World. The general consensus in the scientific community, however, was to associate this type of complexity with Kolmogorov, who was concerned with randomness of a sequence, while Algorithmic Probability became associated with Solomonoff, who focused on prediction using his invention of the universal | + | When Kolmogorov became aware of Solomonoff's work, he acknowledged Solomonoff's priority.<ref>{{cite journal | last1=Kolmogorov | first1=A. | title=Logical basis for information theory and probability theory | journal=IEEE Transactions on Information Theory | volume=14|issue=5 | pages=662–664 | year=1968 | doi =10.1109/TIT.1968.1054210 }}</ref> For several years, Solomonoff's work was better known in the Soviet Union than in the Western World. The general consensus in the scientific community, however, was to associate this type of complexity with Kolmogorov, who was concerned with randomness of a sequence, while Algorithmic Probability became associated with Solomonoff, who focused on prediction using his invention of the universal prior probability distribution. The broader area encompassing descriptional complexity and probability is often called Kolmogorov complexity. The computer scientist Ming Li considers this an example of the [[Matthew effect (sociology)|Matthew effect]]: "... to everyone who has more will be given ..."<ref>{{Cite book |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

| edition = 2nd | | edition = 2nd | ||

| publisher = Springer | | publisher = Springer | ||

Line 81: | Line 95: | ||

| coauthors = Paul Vitanyi | | coauthors = Paul Vitanyi | ||

| title = An Introduction to Kolmogorov Complexity and Its Applications | | title = An Introduction to Kolmogorov Complexity and Its Applications | ||

+ | |page=90 | ||

| date = 1997-02-27 | | date = 1997-02-27 | ||

}}</ref> | }}</ref> | ||

+ | |||

+ | There are several other variants of Kolmogorov complexity or algorithmic information. The most widely used one is based on [[self-delimiting program]]s, and is mainly due to [[Leonid Levin]] (1974). | ||

+ | |||

+ | An axiomatic approach to Kolmogorov complexity based on [[Blum axioms]] (Blum 1967) was introduced by Mark Burgin in the paper presented for publication by Andrey Kolmogorov (Burgin 1982). | ||

==Basic results== | ==Basic results== | ||

In the following discussion, let ''K''(''s'') be the complexity of the string ''s''. | In the following discussion, let ''K''(''s'') be the complexity of the string ''s''. | ||

− | It is not hard to see that the minimal description of a string cannot be too much larger than the string itself - the program GenerateFixedString above that outputs ''s'' is a fixed amount larger than ''s''. | + | It is not hard to see that the minimal description of a string cannot be too much larger than the string itself - the program <code>GenerateFixedString</code> above that outputs ''s'' is a fixed amount larger than ''s''. |

'''Theorem''': There is a constant ''c'' such that | '''Theorem''': There is a constant ''c'' such that | ||

− | : | + | :∀''s''. ''K''(''s'') ≤ |''s''| + ''c''. |

===Incomputability of Kolmogorov complexity=== | ===Incomputability of Kolmogorov complexity=== | ||

− | |||

− | '''Theorem''': ''K'' is not a [[computable function]]. | + | '''Theorem''': There exist strings of arbitrary large Kolmogorov complexity. Formally: for each ''n'' ∈ ℕ, there is a string ''s'' with ''K''(''s'') ≥ ''n''.<ref group="note">However, an ''s'' with ''K''(''s'') = ''n'' needn't exist for every ''n''. For example, if ''n'' isn't a multiple of 7 bits, no [[ASCII]] program can have a length of exactly ''n'' bits.</ref> |

+ | |||

+ | '''Proof:''' Otherwise all infinitely many possible 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 a string ''s'' as input and produces the integer ''K''(''s'') as output. | ||

− | + | The following [[indirect proof|indirect]] '''proof''' 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 1'400'000 bits. | |

+ | Assume for contradiction there is a program | ||

− | '''function''' KolmogorovComplexity('''string | + | '''function''' KolmogorovComplexity('''string''' s) |

− | + | which takes as input a string ''s'' and returns ''K''(''s''); for sake of proof simplicity, assume its length to be 7'000'000'000 bits. | |

+ | Now, consider the following program of length 1'288 bits: | ||

− | '''function''' GenerateComplexString( | + | '''function''' GenerateComplexString() |

'''for''' i = 1 '''to''' infinity: | '''for''' i = 1 '''to''' infinity: | ||

'''for each''' string s '''of''' length exactly i | '''for each''' string s '''of''' length exactly i | ||

− | '''if''' KolmogorovComplexity( | + | '''if''' KolmogorovComplexity(s) >= 8000000000 |

− | '''return | + | '''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 8'000'000'000 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 8'000'000'000 bits. However, the overall length of the above program that produced ''s'' is only 7'001'401'288 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.) | |

− | + | The above proof used 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>State without proof in: [http://www.daimi.au.dk/~bromille/DC05/Kolmogorov.pdf "''Course notes for Data Compression - Kolmogorov complexity''"], 2005, P.B. Miltersen, p.7</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. | |

===Chain rule for Kolmogorov complexity=== | ===Chain rule for Kolmogorov complexity=== | ||

Line 137: | Line 144: | ||

The chain rule for Kolmogorov complexity states that | The chain rule for Kolmogorov complexity states that | ||

− | : | + | :''K''(''X'',''Y'') = ''K''(''X'') + ''K''(''Y''|''X'') + ''O''(log(''K''(''X'',''Y''))). |

It states that the shortest program that reproduces ''X'' and ''Y'' is [[Big-O notation|no more]] than a logarithmic term larger than a program to reproduce ''X'' and a program to reproduce ''Y'' given ''X''. Using this statement, one can define [[Mutual information#Absolute mutual information|an analogue of mutual information for Kolmogorov complexity]]. | It states that the shortest program that reproduces ''X'' and ''Y'' is [[Big-O notation|no more]] than a logarithmic term larger than a program to reproduce ''X'' and a program to reproduce ''Y'' given ''X''. Using this statement, one can define [[Mutual information#Absolute mutual information|an analogue of mutual information for Kolmogorov complexity]]. | ||

==Compression== | ==Compression== | ||

− | It is straightforward to compute upper bounds for | + | 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. |

− | A string ''s'' is compressible by a number ''c'' if it has a description whose length does not exceed | + | 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 ''K''(''s'') ≤ |''s''|-''c''. Otherwise, ''s'' is incompressible by ''c''. A string incompressible by 1 is said to be simply ''incompressible'' – 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<sup>''n''</sup> bit strings of length ''n'', but only 2<sup>''n''</sup> - 1 shorter strings, that is, strings of length less than ''n'', (i.e. with length 0,1,...,''n − 1).<ref group=note>As there are {{nobr|1=''N''<sub>''L''</sub> = 2<sup>''L''</sup>}} strings of length ''L'', the number of strings of lengths {{nowrap|1=''L'' = 0, 1, ..., ''n'' − 1}} is {{nobr|''N''<sub>0</sub> + ''N''<sub>1</sub> + ... + ''N''<sub>''n''−1</sub>}} = {{nobr|2<sup>0</sup> + 2<sup>1</sup> + ... + 2<sup>''n''−1</sup>}}, which is a finite [[geometric series]] with sum {{nobr|2<sup>0</sup> + 2<sup>1</sup> + ... + 2<sup>''n''−1</sup>}} = {{nobr|1 = 2<sup>0</sup> × (1 − 2<sup>''n''</sup>) / (1 − 2) = 2<sup>''n''</sup> − 1}}.</ref> |

− | For the same reason, most strings are complex in the sense that they cannot be significantly compressed | + | For the same reason, most strings are complex in the sense that they cannot be significantly compressed – 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<sup>''n''</sup> bitstrings of length ''n''. The [[Uniform distribution (discrete)|uniform]] [[probability]] distribution on the space of these bitstrings assigns exactly equal weight 2<sup>-''n''</sup> 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 | + | '''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 1 - 2<sup>-''c''+1</sup> + 2<sup>-''n''</sup>. |

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

− | : | + | :1 + 2 + 2<sup>2</sup> + ... + 2<sup>''n''-''c''</sup> = 2<sup>''n''-''c''+1</sup> - 1. |

There remain at least | There remain at least | ||

− | :< | + | :2<sup>''n''</sup> - 2<sup>''n''-''c''+1</sup> + 1 |

− | bitstrings of length ''n'' that are incompressible by ''c''. To determine the probability, divide by < | + | bitstrings of length ''n'' that are incompressible by ''c''. To determine the probability, divide by 2<sup>''n''</sup>. |

==Chaitin's incompleteness theorem== | ==Chaitin's incompleteness theorem== | ||

− | We know that, in the set of all possible strings, most strings are complex in the sense that they cannot be described in any significantly "compressed" way. However, it turns out that the fact that a specific string is complex cannot be formally | + | We know that, in the set of all possible strings, most strings are complex in the sense that they cannot be described in any significantly "compressed" way. However, it turns out that the fact that a specific string is complex cannot be formally proven, if the complexity of the string is above a certain threshold. The precise formalization is as follows. First, fix a particular [[axiomatic system]] '''S''' for the [[natural number]]s. The axiomatic system has to be powerful enough so that, to certain assertions '''A''' about complexity of strings, one can associate a formula '''F'''<sub>'''A'''</sub> in '''S'''. This association must have the following property: |

if '''F'''<sub>'''A'''</sub> is provable from the axioms of '''S''', then the corresponding assertion '''A''' must be true. This "formalization" can be achieved, either by an artificial encoding such as a [[Gödel numbering]], or by a formalization which more clearly respects the intended interpretation of '''S'''. | if '''F'''<sub>'''A'''</sub> is provable from the axioms of '''S''', then the corresponding assertion '''A''' must be true. This "formalization" can be achieved, either by an artificial encoding such as a [[Gödel numbering]], or by a formalization which more clearly respects the intended interpretation of '''S'''. | ||

Line 167: | Line 174: | ||

'''Theorem''': There exists a constant ''L'' (which only depends on the particular axiomatic system and the choice of description language) such that there does not exist a string ''s'' for which the statement | '''Theorem''': There exists a constant ''L'' (which only depends on the particular axiomatic system and the choice of description language) such that there does not exist a string ''s'' for which the statement | ||

− | : | + | :''K''(''s'') ≥ ''L'' (as formalized in '''S''') |

+ | |||

+ | can be proven within the axiomatic system '''S'''. | ||

Note that, by the abundance of nearly incompressible strings, the vast majority of those statements must be true. | Note that, by the abundance of nearly incompressible strings, the vast majority of those statements must be true. | ||

Line 194: | Line 203: | ||

'''if''' NthProofProvesComplexityFormula(i) '''and''' ComplexityLowerBoundNthProof(i) ≥ ''n'' | '''if''' NthProofProvesComplexityFormula(i) '''and''' ComplexityLowerBoundNthProof(i) ≥ ''n'' | ||

'''return''' StringNthProof(''i'') | '''return''' StringNthProof(''i'') | ||

− | |||

Given an ''n'', this program tries every proof until it finds a string and a proof in the [[formal system]] '''S''' of the formula ''K''(''s'') ≥ ''L'' for some ''L'' ≥ ''n''. The program terminates by our '''Assumption (X)'''. Now, this program has a length ''U''. There is an integer ''n''<sub>0</sub> such that ''U'' + log<sub>2</sub>(''n''<sub>0</sub>) + ''C'' < ''n''<sub>0</sub>, where ''C'' is the overhead cost of | Given an ''n'', this program tries every proof until it finds a string and a proof in the [[formal system]] '''S''' of the formula ''K''(''s'') ≥ ''L'' for some ''L'' ≥ ''n''. The program terminates by our '''Assumption (X)'''. Now, this program has a length ''U''. There is an integer ''n''<sub>0</sub> such that ''U'' + log<sub>2</sub>(''n''<sub>0</sub>) + ''C'' < ''n''<sub>0</sub>, where ''C'' is the overhead cost of | ||

Line 200: | Line 208: | ||

'''function''' GenerateProvablyParadoxicalString() | '''function''' GenerateProvablyParadoxicalString() | ||

'''return''' GenerateProvablyComplexString(''n''<sub>0</sub>) | '''return''' GenerateProvablyComplexString(''n''<sub>0</sub>) | ||

− | |||

− | The program GenerateProvablyParadoxicalString outputs a string ''s'' for which there exists an ''L'' such that ''K''(''s'') ≥ ''L'' can be formally proved in '''S''' with ''L'' ≥ ''n''<sub>0</sub>. In particular, ''K''(''s'') ≥ ''n''<sub>0</sub> is true. However, ''s'' is also described by a program of length ''U'' + log<sub>2</sub>(''n''<sub>0</sub>) + ''C'', so its complexity is less than ''n''<sub>0</sub>. This contradiction proves '''Assumption (X)''' cannot hold. | + | (note that ''n''<sub>0</sub> is hard-coded into the above function, and the summand log<sub>2</sub>(''n''<sub>0</sub>) already allows for its encoding). The program GenerateProvablyParadoxicalString outputs a string ''s'' for which there exists an ''L'' such that ''K''(''s'') ≥ ''L'' can be formally proved in '''S''' with ''L'' ≥ ''n''<sub>0</sub>. In particular, ''K''(''s'') ≥ ''n''<sub>0</sub> is true. However, ''s'' is also described by a program of length ''U'' + log<sub>2</sub>(''n''<sub>0</sub>) + ''C'', so its complexity is less than ''n''<sub>0</sub>. This contradiction proves '''Assumption (X)''' cannot hold. |

Similar ideas are used to prove the properties of [[Chaitin's constant]]. | Similar ideas are used to prove the properties of [[Chaitin's constant]]. | ||

Line 210: | Line 217: | ||

==Kolmogorov randomness== | ==Kolmogorov randomness== | ||

− | + | ''Kolmogorov randomness'' – also called ''algorithmic randomness'' – defines a string (usually of [[bit]]s) as being [[randomness|random]] if and only if it is shorter than any [[computer program]] that can produce that string. To make this precise, a [[universal computer]] (or universal Turing machine) must be specified, so that "program" means a program for this universal machine. A random string in this sense is "incompressible" in that it is impossible to "compress" the string into a program whose length is shorter than the length of the string itself. A [[counting argument]] is used to show that, for any universal computer, there is at least one algorithmically random string of each length. Whether any particular string is random, however, depends on the specific universal computer that is chosen. | |

− | ''Kolmogorov randomness'' | + | |

+ | This definition can be extended to define a notion of randomness for ''infinite'' sequences from a finite alphabet. These [[algorithmically random sequence]]s can be defined in three equivalent ways. One way uses an effective analogue of [[measure theory]]; another uses effective [[Martingale (probability theory)|martingales]]. The third way defines an infinite sequence to be random if the prefix-free Kolmogorov complexity of its initial segments grows quickly enough - there must be a constant ''c'' such that the complexity of an initial segment of length ''n'' is always at least ''n''−''c''. This definition, unlike the definition of randomness for a finite string, is not affected by which universal machine is used to define prefix-free Kolmogorov complexity. | ||

+ | <ref>{{cite doi | 10.1016/S0019-9958(66)80018-9}}</ref> | ||

== Relation to entropy == | == Relation to entropy == | ||

− | It can be shown<ref> | + | For dynamical systems, entropy rate and algorithmic complexity of the trajectories are related by a theorem of Brudno, that the equality K(x;T) = h(T) holds for almost all x.<ref>{{cite journal |authors=Stefano Galatolo, Mathieu Hoyrup, Cristóbal Rojas |title=Effective symbolic dynamics, random points, statistical behavior, complexity and entropy | journal=Information and Computation | volume=208 | pages=23-41 | year=2010| url=http://www.loria.fr/~hoyrup/random_ergodic.pdf}}</ref> |

+ | |||

+ | It can be shown<ref>{{cite journal |author=Alexei Kaltchenko |title=Algorithms for Estimating Information Distance with Application to Bioinformatics and Linguistics |journal=CoRR |volume=cs.CC/0404039 |year=2004 |url=http://arxiv.org/pdf/cs.CC/0404039 |url=http://arxiv.org/abs/cs.CC/0404039}}</ref> that for the output of [[Markov information source]]s, Kolmogorov complexity is related to the [[Entropy (information theory)|entropy]] of the information source. More precisely, the Kolmogorov complexity of the output of a Markov information source, normalized by the length of the output, converges almost surely (as the length of the output goes to infinity) to the [[Entropy (information theory)|entropy]] of the source. | ||

==See also== | ==See also== | ||

Line 226: | Line 237: | ||

==Notes== | ==Notes== | ||

− | {{Reflist|group= | + | {{Reflist|group=note}} |

==References== | ==References== | ||

− | {{Reflist}} | + | {{Reflist|colwidth=30em}} |

* {{cite journal | authorlink=Manuel Blum|last=Blum | title=On the size of machines | journal=Information and Control |first= M. | volume=11 | issue=3 | pages=257 | year=1967 | doi = 10.1016/S0019-9958(67)90546-3 }} | * {{cite journal | authorlink=Manuel Blum|last=Blum | title=On the size of machines | journal=Information and Control |first= M. | volume=11 | issue=3 | pages=257 | year=1967 | doi = 10.1016/S0019-9958(67)90546-3 }} | ||

+ | * Brudno, A. Entropy and the complexity of the trajectories of a dynamical system., Transactions of the Moscow Mathematical Society, 2:127{151, 1983. | ||

* Burgin, M. (1982), "Generalized Kolmogorov complexity and duality in theory of computations", ''Notices of the Russian Academy of Sciences'', v.25, No. 3, pp. 19–23. | * Burgin, M. (1982), "Generalized Kolmogorov complexity and duality in theory of computations", ''Notices of the Russian Academy of Sciences'', v.25, No. 3, pp. 19–23. | ||

* Cover, Thomas M. and Thomas, Joy A., ''Elements of information theory'', 1st Edition. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6. 2nd Edition. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4. | * Cover, Thomas M. and Thomas, Joy A., ''Elements of information theory'', 1st Edition. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6. 2nd Edition. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4. | ||

− | |||

− | |||

* Lajos, Rónyai and Gábor, Ivanyos and Réka, Szabó, ''Algoritmusok''. TypoTeX, 1999. ISBN 963-279-014-6 | * Lajos, Rónyai and Gábor, Ivanyos and Réka, Szabó, ''Algoritmusok''. TypoTeX, 1999. ISBN 963-279-014-6 | ||

* Li, Ming and Vitányi, Paul, ''An Introduction to Kolmogorov Complexity and Its Applications'', Springer, 1997. [http://citeseer.ist.psu.edu/li97introduction.html Introduction chapter full-text]. | * Li, Ming and Vitányi, Paul, ''An Introduction to Kolmogorov Complexity and Its Applications'', Springer, 1997. [http://citeseer.ist.psu.edu/li97introduction.html Introduction chapter full-text]. | ||

Line 261: | Line 271: | ||

[[Category:Descriptive complexity]] | [[Category:Descriptive complexity]] | ||

[[Category:Measures of complexity]] | [[Category:Measures of complexity]] | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− |

## Revision as of 08:22, 18 February 2014

Template:Distinguish
In algorithmic information theory (a subfield of computer science and mathematics), the **Kolmogorov complexity** (also known as **descriptive complexity**, **Kolmogorov–Chaitin complexity**, **algorithmic entropy**, or **program-size complexity**) of an object, such as a piece of text, is a measure of the computability resources needed to specify the object. It is named after Andrey Kolmogorov, who first published on the subject in 1963.^{[1]}^{[2]}

For example, consider the following two strings of 32 lowercase letters and digits:

abababababababababababababababab

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

The first string has a short English-language description, namely "ab 16 times", which consists of **11** characters. The second one has no obvious simple description (using the same character set) other than writing down the string itself, which has **32** characters.

More formally, the complexity of a string is the length of the shortest possible description of the string in some fixed universal description language (the sensitivity of complexity relative to the choice of description language is discussed below). It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes larger than the length of the string itself. Strings, like the *abab* example above, whose Kolmogorov complexity is small relative to the string's size are not considered to be complex.

The notion of the Kolmogorov complexity can be used to state and prove impossibility results akin to Gödel's incompleteness theorem and Turing's halting problem.

## Contents

## Definition

The Kolmogorov complexity can be defined for any mathematical object, however for simplicity, it will be defined here for strings. We must first specify a description language for strings. Such a description language can be based on any computer programming language, such as Lisp, Pascal, or Java virtual machine bytecode. If **P** is a program which outputs a string *x*, then **P** is a description of *x*. The length of the description is just the length of **P** as a character string, multiplied by the number of bits in a character (e.g. 7 for ASCII).

We could, alternatively, choose an encoding for Turing machines, where an *encoding* is a function which associates to each Turing Machine **M** a bitstring <**M**>. If **M** is a Turing Machine which, on input *w*, outputs string *x*, then the concatenated string <**M**> *w* is a description of *x*. For theoretical analysis, this approach is more suited for constructing detailed formal proofs and is generally preferred in the research literature. In this article, an informal approach is discussed.

Any string *s* has at least one description, namely the program:

functionGenerateFixedString()returns

If a description of *s*, *d*(*s*), is of minimal length (i.e. it uses the fewest bits), it is called a **minimal description** of *s*. Thus, the length of *d*(*s*) (i.e. the number of bits in the description) is the **Kolmogorov complexity** of *s*, written *K*(*s*). Symbolically,

*K*(*s*) = |*d*(*s*)|.

The length of the shortest description will depend on the choice of description language; but the effect of changing languages is bounded (a result called the *invariance theorem*).

## Invariance theorem

### Informal treatment

There are some description languages which are optimal, in the following sense: given any description of an object in a description language, I can use that description in my optimal description language with a constant overhead. The constant depends only on the languages involved, not on the description of the object, or the object being described.

Here is an example of an optimal description language. A description will have two parts:

- The first part describes another description language.
- The second part is a description of the object in that language.

In more technical terms, the first part of a description is a computer program, with the second part being the input to that computer program which produces the object as output.

**The invariance theorem follows:** Given any description language *L*, the optimal description language is at least as efficient as *L*, with some constant overhead.

**Proof:** Any description *D* in *L* can be converted into a description in the optimal language by first describing *L* as a computer program *P* (part 1), and then using the original description *D* as input to that program (part 2). The
total length of this new description *D*’ is (approximately):

- |
*D*’| = |*P*| + |*D*|

The length of *P* is a constant that doesn't depend on *D*. So, there is at most a constant overhead, regardless of the object described. Therefore, the optimal language is universal up to this additive constant.

### A more formal treatment

**Theorem**: If *K*_{1} and *K*_{2} are the complexity functions relative to Turing complete description languages *L*_{1} and *L*_{2}, then there is a constant *c* – which depends only on the languages *L*_{1} and *L*_{2} chosen – such that

- ∀
*s*. -*c*≤*K*_{1}(*s*) -*K*_{2}(*s*) ≤*c*.

**Proof**: By symmetry, it suffices to prove that there is some constant *c* such that for all strings *s*

*K*_{1}(*s*) ≤*K*_{2}(*s*) +*c*.

Now, suppose there is a program in the language *L*_{1} which acts as an interpreter for *L*_{2}:

functionInterpretLanguage(stringp)

where *p* is a program in *L*_{2}. The interpreter is characterized by the following property:

- Running
`InterpretLanguage`

on input*p*returns the result of running*p*.

Thus, if **P** is a program in *L*_{2} which is a minimal description of *s*, then `InterpretLanguage`

(**P**) returns the string *s*. The length of this description of *s* is the sum of

- The length of the program
`InterpretLanguage`

, which we can take to be the constant*c*. - The length of
**P**which by definition is*K*_{2}(*s*).

This proves the desired upper bound.

## History and context

Algorithmic information theory is the area of computer science that studies Kolmogorov complexity and other complexity measures on strings (or other data structures).

The concept and theory of Kolmogorov Complexity is based on a crucial theorem first discovered by Ray Solomonoff, who published it in 1960, describing it in "A Preliminary Report on a General Theory of Inductive Inference"^{[3]} as part of his invention of algorithmic probability. He gave a more complete description in his 1964 publications, "A Formal Theory of Inductive Inference," Part 1 and Part 2 in *Information and Control*.^{[4]}^{[5]}

Andrey Kolmogorov later independently published this theorem in *Problems Inform. Transmission*,^{[6]} Gregory Chaitin also presents this theorem in *J. ACM* – Chaitin's paper was submitted October 1966 and revised in December 1968, and cites both Solomonoff's and Kolmogorov's papers.^{[7]}

The theorem says that, among algorithms that decode strings from their descriptions (codes), there exists an optimal one. This algorithm, for all strings, allows codes as short as allowed by any other algorithm up to an additive constant that depends on the algorithms, but not on the strings themselves. Solomonoff used this algorithm, and the code lengths it allows, to define a "universal probability" of a string on which inductive inference of the subsequent digits of the string can be based. Kolmogorov used this theorem to define several functions of strings, including complexity, randomness, and information.

When Kolmogorov became aware of Solomonoff's work, he acknowledged Solomonoff's priority.^{[8]} For several years, Solomonoff's work was better known in the Soviet Union than in the Western World. The general consensus in the scientific community, however, was to associate this type of complexity with Kolmogorov, who was concerned with randomness of a sequence, while Algorithmic Probability became associated with Solomonoff, who focused on prediction using his invention of the universal prior probability distribution. The broader area encompassing descriptional complexity and probability is often called Kolmogorov complexity. The computer scientist Ming Li considers this an example of the Matthew effect: "... to everyone who has more will be given ..."^{[9]}

There are several other variants of Kolmogorov complexity or algorithmic information. The most widely used one is based on self-delimiting programs, and is mainly due to Leonid Levin (1974).

An axiomatic approach to Kolmogorov complexity based on Blum axioms (Blum 1967) was introduced by Mark Burgin in the paper presented for publication by Andrey Kolmogorov (Burgin 1982).

## Basic results

In the following discussion, let *K*(*s*) be the complexity of the string *s*.

It is not hard to see that the minimal description of a string cannot be too much larger than the string itself - the program `GenerateFixedString`

above that outputs *s* is a fixed amount larger than *s*.

**Theorem**: There is a constant *c* such that

- ∀
*s*.*K*(*s*) ≤ |*s*| +*c*.

### Incomputability of Kolmogorov complexity

**Theorem**: There exist strings of arbitrary large Kolmogorov complexity. Formally: for each *n* ∈ ℕ, there is a string *s* with *K*(*s*) ≥ *n*.^{[note 1]}

**Proof:** Otherwise all infinitely many possible strings could be generated by the finitely many^{[note 2]} programs with a complexity below *n* bits.

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

The following indirect **proof** uses a simple Pascal-like language to denote programs; for sake of proof simplicity assume its description (i.e. an interpreter) to have a length of 1'400'000 bits.
Assume for contradiction there is a program

functionKolmogorovComplexity(strings)

which takes as input a string *s* and returns *K*(*s*); for sake of proof simplicity, assume its length to be 7'000'000'000 bits.
Now, consider the following program of length 1'288 bits:

functionGenerateComplexString()fori = 1toinfinity:for eachstring soflength exactly iifKolmogorovComplexity(s) >= 8000000000returns

Using `KolmogorovComplexity`

as a subroutine, the program tries every string, starting with the shortest, until it returns a string with Kolmogorov complexity at least 8'000'000'000 bits,^{[note 3]} i.e. a string that cannot be produced by any program shorter than 8'000'000'000 bits. However, the overall length of the above program that produced *s* is only 7'001'401'288 bits,^{[note 4]} which is a contradiction. (If the code of `KolmogorovComplexity`

is shorter, the contradiction remains. If it is longer, the constant used in `GenerateComplexString`

can always be changed appropriately.)

The above proof used a contradiction similar to that of the Berry paradox: "_{1}The _{2}smallest _{3}positive _{4}integer _{5}that _{6}cannot _{7}be _{8}defined _{9}in _{10}fewer _{11}than _{12}twenty _{13}English _{14}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-equivalent.^{[10]}

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

### Chain rule for Kolmogorov complexity

{{#invoke:main|main}} The chain rule for Kolmogorov complexity states that

*K*(*X*,*Y*) =*K*(*X*) +*K*(*Y*|*X*) +*O*(log(*K*(*X*,*Y*))).

It states that the shortest program that reproduces *X* and *Y* is no more than a logarithmic term larger than a program to reproduce *X* and a program to reproduce *Y* given *X*. Using this statement, one can define an analogue of mutual information for Kolmogorov complexity.

## Compression

It is straightforward to compute upper bounds for *K*(*s*) – simply 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.

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 *K*(*s*) ≤ |*s*|-*c*. Otherwise, *s* is incompressible by *c*. A string incompressible by 1 is said to be simply *incompressible* – by the pigeonhole principle, which applies because every compressed string maps to only one uncompressed string, incompressible strings 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 − 1). ^{[note 5]}*

For the same reason, most strings are complex in the sense that they cannot be significantly compressed – 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 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 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:

- 1 + 2 + 2
^{2}+ ... + 2^{n-c}= 2^{n-c+1}- 1.

There remain at least

- 2
^{n}- 2^{n-c+1}+ 1

bitstrings of length *n* that are incompressible by *c*. To determine the probability, divide by 2^{n}.

## Chaitin's incompleteness theorem

We know that, in the set of all possible strings, most strings are complex in the sense that they cannot be described in any significantly "compressed" way. However, it turns out that the fact that a specific string is complex cannot be formally proven, if the complexity of the string is above a certain threshold. The precise formalization is as follows. First, fix a particular axiomatic system **S** for the natural numbers. The axiomatic system has to be powerful enough so that, to certain assertions **A** about complexity of strings, one can associate a formula **F**_{A} in **S**. This association must have the following property:

if **F**_{A} is provable from the axioms of **S**, then the corresponding assertion **A** must be true. This "formalization" can be achieved, either by an artificial encoding such as a Gödel numbering, or by a formalization which more clearly respects the intended interpretation of **S**.

**Theorem**: There exists a constant *L* (which only depends on the particular axiomatic system and the choice of description language) such that there does not exist a string *s* for which the statement

*K*(*s*) ≥*L*(as formalized in**S**)

can be proven within the axiomatic system **S**.

Note that, by the abundance of nearly incompressible strings, the vast majority of those statements must be true.

The proof of this result is modeled on a self-referential construction used in Berry's paradox. The proof is by contradiction. If the theorem were false, then

**Assumption (X)**: For any integer*n*there exists a string*s*for which there is a proof in**S**of the formula "*K*(*s*) ≥*n*" (which we assume can be formalized in**S**).

We can find an effective enumeration of all the formal proofs in **S** by some procedure

functionNthProof(intn)

which takes as input *n* and outputs some proof. This function enumerates all proofs. Some of these are proofs for formulas we do not care about here, since every possible proof in the language of **S** is produced for some *n*. Some of these are complexity formulas of the form *K*(*s*) ≥ *n* where *s* and *n* are constants in the language of **S**. There is a program

functionNthProofProvesComplexityFormula(intn)

which determines whether the *n*th proof actually proves a complexity formula *K*(*s*) ≥ *L*. The strings *s*, and the integer *L* in turn, are computable by programs:

functionStringNthProof(intn)

functionComplexityLowerBoundNthProof(intn)

Consider the following program

functionGenerateProvablyComplexString(intn)fori = 1 to infinity:ifNthProofProvesComplexityFormula(i)andComplexityLowerBoundNthProof(i) ≥nreturnStringNthProof(i)

Given an *n*, this program tries every proof until it finds a string and a proof in the formal system **S** of the formula *K*(*s*) ≥ *L* for some *L* ≥ *n*. The program terminates by our **Assumption (X)**. Now, this program has a length *U*. There is an integer *n*_{0} such that *U* + log_{2}(*n*_{0}) + *C* < *n*_{0}, where *C* is the overhead cost of

functionGenerateProvablyParadoxicalString()returnGenerateProvablyComplexString(n_{0})

(note that *n*_{0} is hard-coded into the above function, and the summand log_{2}(*n*_{0}) already allows for its encoding). The program GenerateProvablyParadoxicalString outputs a string *s* for which there exists an *L* such that *K*(*s*) ≥ *L* can be formally proved in **S** with *L* ≥ *n*_{0}. In particular, *K*(*s*) ≥ *n*_{0} is true. However, *s* is also described by a program of length *U* + log_{2}(*n*_{0}) + *C*, so its complexity is less than *n*_{0}. This contradiction proves **Assumption (X)** cannot hold.

Similar ideas are used to prove the properties of Chaitin's constant.

## Minimum message length

The minimum message length principle of statistical and inductive inference and machine learning was developed by C.S. Wallace and D.M. Boulton in 1968. MML is Bayesian (i.e. it incorporates prior beliefs) and information-theoretic. It has the desirable properties of statistical invariance (i.e. the inference transforms with a re-parametrisation, such as from polar coordinates to Cartesian coordinates), statistical consistency (i.e. even for very hard problems, MML will converge to any underlying model) and efficiency (i.e. the MML model will converge to any true underlying model about as quickly as is possible). C.S. Wallace and D.L. Dowe (1999) showed a formal connection between MML and algorithmic information theory (or Kolmogorov complexity).

## Kolmogorov randomness

*Kolmogorov randomness* – also called *algorithmic randomness* – defines a string (usually of bits) as being random if and only if it is shorter than any computer program that can produce that string. To make this precise, a universal computer (or universal Turing machine) must be specified, so that "program" means a program for this universal machine. A random string in this sense is "incompressible" in that it is impossible to "compress" the string into a program whose length is shorter than the length of the string itself. A counting argument is used to show that, for any universal computer, there is at least one algorithmically random string of each length. Whether any particular string is random, however, depends on the specific universal computer that is chosen.

This definition can be extended to define a notion of randomness for *infinite* sequences from a finite alphabet. These algorithmically random sequences can be defined in three equivalent ways. One way uses an effective analogue of measure theory; another uses effective martingales. The third way defines an infinite sequence to be random if the prefix-free Kolmogorov complexity of its initial segments grows quickly enough - there must be a constant *c* such that the complexity of an initial segment of length *n* is always at least *n*−*c*. This definition, unlike the definition of randomness for a finite string, is not affected by which universal machine is used to define prefix-free Kolmogorov complexity.
^{[11]}

## Relation to entropy

For dynamical systems, entropy rate and algorithmic complexity of the trajectories are related by a theorem of Brudno, that the equality K(x;T) = h(T) holds for almost all x.^{[12]}

It can be shown^{[13]} that for the output of Markov information sources, Kolmogorov complexity is related to the entropy of the information source. More precisely, the Kolmogorov complexity of the output of a Markov information source, normalized by the length of the output, converges almost surely (as the length of the output goes to infinity) to the entropy of the source.

## See also

- Berry paradox
- Data compression
- Inductive inference
- Kolmogorov structure function
- Important publications in algorithmic information theory
- Levenshtein distance
- Grammar induction

## Notes

- ↑ However, an
*s*with*K*(*s*) =*n*needn't exist for every*n*. For example, if*n*isn't a multiple of 7 bits, no ASCII program can have a length of exactly*n*bits. - ↑ There are 1 + 2 + 2
^{2}+ 2^{3}+ ... + 2^{n}= 2^{n+1}− 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. - ↑ By the previous theorem, such a string exists, hence the
`for`

loop will eventually terminate. - ↑ including the language interpreter and the subroutine code for
`KolmogorovComplexity`

- ↑ As there are Template:Nobr strings of length
*L*, the number of strings of lengths*L*= 0, 1, ...,*n*− 1 is Template:Nobr = Template:Nobr, which is a finite geometric series with sum Template:Nobr = Template:Nobr.

## References

- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }} revision, Nov., 1960.
- ↑ Template:Cite doi
- ↑ Template:Cite doi
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ Template:Cite doi
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ State without proof in: "
*Course notes for Data Compression - Kolmogorov complexity*", 2005, P.B. Miltersen, p.7 - ↑ Template:Cite doi
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- Brudno, A. Entropy and the complexity of the trajectories of a dynamical system., Transactions of the Moscow Mathematical Society, 2:127{151, 1983.
- Burgin, M. (1982), "Generalized Kolmogorov complexity and duality in theory of computations",
*Notices of the Russian Academy of Sciences*, v.25, No. 3, pp. 19–23. - Cover, Thomas M. and Thomas, Joy A.,
*Elements of information theory*, 1st Edition. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6. 2nd Edition. New York: Wiley-Interscience, 2006. ISBN 0-471-24195-4. - Lajos, Rónyai and Gábor, Ivanyos and Réka, Szabó,
*Algoritmusok*. TypoTeX, 1999. ISBN 963-279-014-6 - Li, Ming and Vitányi, Paul,
*An Introduction to Kolmogorov Complexity and Its Applications*, Springer, 1997. Introduction chapter full-text. - Yu Manin,
*A Course in Mathematical Logic*, Springer-Verlag, 1977. ISBN 978-0-7204-2844-5 - Sipser, Michael,
*Introduction to the Theory of Computation*, PWS Publishing Company, 1997. ISBN 0-534-95097-3. - Wallace, C. S. and Dowe, D. L., Minimum Message Length and Kolmogorov Complexity, Computer Journal, Vol. 42, No. 4, 1999).

## External links

- The Legacy of Andrei Nikolaevich Kolmogorov
- Chaitin's online publications
- Solomonoff's IDSIA page
- Generalizations of algorithmic information by J. Schmidhuber
- Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd Edition, Springer Verlag, 1997.
- Tromp's lambda calculus computer model offers a concrete definition of K()
- Universal AI based on Kolmogorov Complexity ISBN 3-540-22139-5 by M. Hutter: ISBN 3-540-22139-5
- David Dowe's Minimum Message Length (MML) and Occam's razor pages.
- P. Grunwald, M. A. Pitt and I. J. Myung (ed.), Advances in Minimum Description Length: Theory and Applications, M.I.T. Press, April 2005, ISBN 0-262-07262-9.