User:Brbauwens/sandbox

We now use Young's inequality, which states that

Variants of Kolmogorov complexity

The standard definition of Kolmogorov complexity considers Turing machines mapping strings to strings. When dealing with infinite random sequences or probabilistic oracles, machines are needed that during the computation request more input and/or gradually append output. Changing the type of Turing machines, one obtains variants of Kolmogorov complexity. Many quantitative results such as the Coding Theorem and the chain rule for Kolmogorov complexity can be tightened with appropriate notions of Kolmogorov complexity.

General definition of Kolmogorov complexity

A machine U that associates several outputs to a program, no longer defines a partial function but a relation U on strings interpreted as programs and outputs. Given a machine U of some type X, the corresponding Kolmogorov complexity K_X(x) of a bitstring x is given by the smallest length of an input on U that has an associated output x:

    $K_{X}(x)=\min\{|p|:(p,x)\in U\}$.

For all common types of machines X, there exist machines U for which K_X(x) is minimal up to a constant: for any other machine there exist a number c such that its complexity K'_(x) satisfies K_X ≤ K'_X(x) + c. In our definition of K_X(x) we assume such an optimal machine.

We compare several restrictions on sets U, each restriction defines a machine of some type.

Plain complexity C(x)

Plain Turing machines define the type of Kolmogorov complexity mostly used in Theoretical computer science and was introduced by Andrey Kolmogorov. In this definition the relation U defines a function. Thus if $(p_{1},x_{1})\in U$ and $(p_{2},x_{2})\in U$ then

     $p_{1}=p_{2}\;\;\Rightarrow \;\;x_{1}=x_{2}$.

The machine model is given by Turing machines with a 3-symbol tape (blanc-zero-one). At the start of the computation the tape contains a binary program and all other cells are blanc. When the computation unit of the Turing machines obtains a halting state, a unique output is associated to the program. Such output is always a (finite) string.

Prefix complexity K(x)

There exist two types of machines that define the same notion of complexity: prefix-free machines and prefix-stable machines. Prefix-free machines

In algorithmic information theory (a subfield of computer science), 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 computational resources needed to specify the object. It is named after Andrey Kolmogorov, who first published on the subject in 1963.

strings 

Definition

$\forall s\ |K_{1}(s)-K_{2}(s)|\leq c.$

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

$K_{1}(s)\leq K_{2}(s)+c.$

Now, suppose there is a program in the language L₁ which acts as an interpreter for L₂:

  function InterpretLanguage(string p)

where p is a program in L₂. 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₂ 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

1. The length of the program InterpretLanguage, which we can take to be the constant c.
2. The length of P which by definition is K₂(s).

This proves the desired upper bound.

See also invariance theorem.

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" 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.

Andrey Kolmogorov later independently published this theorem in Problems Inform. Transmission, 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.

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. 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.

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).

Some consider that naming the concept "Kolmogorov complexity" is an example of the Matthew effect.

Theorem: K is not a computable function.

Chain rule for Kolmogorov complexity

Main article: Chain rule for Kolmogorov complexity

The chain rule for Kolmogorov complexity states that

$K(X,Y)=K(X)+K(Y|X)+O(\log(K(X,Y))).\quad$

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.

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.

See also

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

References

• Blum, M. (1967). "On the size of machines". Information and Control. 11 (3): 257–265. 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.
• 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.
• Kolmogorov, Andrei N. (1963). "On Tables of Random Numbers". Sankhyā Ser. A. 25: 369–375. MR 0178484.
• Kolmogorov, Andrei N. (1998). "On Tables of Random Numbers". Theoretical Computer Science. 207 (2): 387–395. doi:10.1016/S0304-3975(98)00075-9. MR 1643414.
• 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.

* * Category:Computability theory Category:Descriptive complexity Category:Measures of complexity