This image illustrates part of the Mandelbrot set fractal. Simply storing the 24-bit color of each pixel in this image would require 23 million bytes, but a small computer program can reproduce these 23 MB using the definition of the Mandelbrot set and the corner coordinates of the image. Thus, the Kolmogorov complexity of this image is much less than 23 MB in any pragmatic model of computation. PNG's general-purpose image compression only reduces it to 1.6 MB, smaller than the raw data but much larger than the Kolmogorov complexity.
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. It is named after Andrey Kolmogorov, who first published on the subject in 1963[1][2] and is a generalization of classical information theory.
The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to Cantor's diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem.
In particular, no program P computing a lower bound for each text's Kolmogorov complexity can return a value essentially larger than P's own length (see section § Chaitin's incompleteness theorem); hence no single program can compute the exact Kolmogorov complexity for infinitely many texts.
^Kolmogorov, Andrey (1963). "On Tables of Random Numbers". Sankhyā Ser. A. 25: 369–375. MR 0178484.
^Kolmogorov, Andrey (1998). "On Tables of Random Numbers". Theoretical Computer Science. 207 (2): 387–395. doi:10.1016/S0304-3975(98)00075-9. MR 1643414.
and 23 Related for: Kolmogorov complexity information
information theory (a subfield of computer science and mathematics), the Kolmogorovcomplexity of an object, such as a piece of text, is the length of a shortest...
kinds of Kolmogorovcomplexity are studied: the uniform complexity, prefix complexity, monotone complexity, time-bounded Kolmogorovcomplexity, and space-bounded...
mechanics, algorithmic information theory and computational complexity. Andrey Kolmogorov was born in Tambov, about 500 kilometers south-southeast of...
that the Kolmogorovcomplexity is not computable. The proof by contradiction shows that if it were possible to compute the Kolmogorovcomplexity, then it...
machine used to define Kolmogorovcomplexity, but any choice gives identical asymptotic results because the Kolmogorovcomplexity of a string is invariant...
maximal Kolmogorovcomplexity. The Kolmogorov structure function of an individual data string expresses the relation between the complexity level constraint...
area. The field of Kolmogorovcomplexity and algorithmic randomness was developed during the 1960s and 1970s by Chaitin, Kolmogorov, Levin, Martin-Löf...
probability is closely related to the concept of Kolmogorovcomplexity. Kolmogorov's introduction of complexity was motivated by information theory and problems...
The chain rule[citation needed] for Kolmogorovcomplexity is an analogue of the chain rule for information entropy, which states: H ( X , Y ) = H ( X...
extended Turing test. or by tests which are completely derived from Kolmogorovcomplexity. Other related tests in this line are presented by Hernandez-Orallo...
For finite sequences, Kolmogorov defines randomness of a binary string of length n as the entropy (or Kolmogorovcomplexity) normalized by the length...
a space of outcomes Ω. Dembski's proposed test is based on the Kolmogorovcomplexity of a pattern T that is exhibited by an event E that has occurred...
the Kolmogorovcomplexity theory, named for Andrey Kolmogorov. One of the first uses of the incompressibility method with Kolmogorovcomplexity in the...
indeed, this result is used to define the concept of randomness in Kolmogorovcomplexity. It is provably impossible to create an algorithm that can losslessly...
{some\ c.e.} \ s\mathrm {-gale\ succeeds\ strongly\ on\ } X\}} . Kolmogorovcomplexity can be thought of as a lower bound on the algorithmic compressibility...
algorithmic probability in 1960, publishing the theorem that launched Kolmogorovcomplexity and algorithmic information theory. He first described these results...
be deployed in practice. It differs from the related concept of Kolmogorovcomplexity in that it does not require use of a Turing-complete language to...
linear complexity, provide spectral measures of randomness. T. Beth and Z-D. Dai purported to show that Kolmogorovcomplexity and linear complexity are practically...
known as algorithmic (Solomonoff–Kolmogorov–Chaitin, Kolmogorov or program-size) complexity together with Andrei Kolmogorov and Ray Solomonoff. Along with...
good solution. Almost all objective functions are of such high Kolmogorovcomplexity that they cannot be stored in a particular computer. More precisely...
Kolmogorovcomplexity. Together with Leonid A. Levin, he established basic properties of prefix complexity including the formula for the complexity of...
V(x)=U(h(x))} . An optimal machine is a universal machine that achieves the Kolmogorovcomplexity invariance bound, i.e. for every machine V, there exists c such...
Invariance of domain, a theorem in topology A theorem pertaining to Kolmogorovcomplexity A result in classical mechanics for adiabatic invariants A theorem...
Global Information