Editing Kolmogorov complexity (section)

{{short description|Measure of algorithmic complexity}}
[[Image:Mandelpart2 red.png|right|thumb|upright=1.4|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<!--3200 × 2400 × 3 = 23.04e6-->, but a small computer program can reproduce these 23 MB using the definition of the Mandelbrot set, the corner coordinates of the image and the parameters of the color mapping. Thus, the Kolmogorov complexity of this image is much less than 23 MB in any pragmatic [[model of computation]]. [[Portable Network Graphics|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 [[computation]]al 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<ref>{{cite journal |author-link=Andrey Kolmogorov |first=Andrey|last=Kolmogorov |date=Dec 1963 |title=On Tables of Random Numbers| journal=Sankhyā: The Indian Journal of Statistics, Series A (1961-2002) |volume=25 |issue=4 |pages=369–375 |mr=178484 |jstor=25049284 |issn=0581-572X }}</ref><ref>{{cite journal|author-link=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|doi-access=free}}</ref> and is a generalization of classical information theory.

The notion of Kolmogorov complexity can be used to state and [[Proof of impossibility|prove impossibility]] results akin to [[Cantor's diagonal argument]], [[Gödel's incompleteness theorem]], and [[halting problem|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''<nowiki>'</nowiki>s own length (see section {{slink||Chaitin's incompleteness theorem}}); hence no single program can compute the exact Kolmogorov complexity for infinitely many texts. Kolmogorov complexity is the length of the ultimately compressed version of a file (i.e., anything which can be put in a computer). Formally, it is the length of a shortest program from which the file can be reconstructed. While Kolmogorov complexity is uncomputable, various approaches have been proposed and reviewed.<ref name="zenil20202">{{cite journal |last1=Zenil |first1=Hector |year=2020 |title=A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions |journal=Entropy |volume=22 |issue=6 |pages=612 |doi=10.3390/e22060612 |doi-access=free |pmid=33286384 |pmc=7517143 }}</ref>