This image shows a fraction of the Mandelbrot collection fractal. Separately saving all 24-bit color pixels in this image would cost 1.62 million bits. A small computer program can reproduce these 1.62 million bits using the definition of the Mandelbrot collection. Thus, the Kolmogorov complex of this raw file is much less than 1.62 million.
The Kolmogorov complexity or algorithmic complexity (also known as the descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy or program size complexity) is the extent to which a model or system can be described in mathematical or algorithmic terms. This is the minimum description length principle (Minimum Description Length Principle), the length of the shortest computer program to generate a data structure. This part of the algorithmic information theory (a part of computer science) is named after Russian mathematician Andrej Kolmogorov.
For example, take the following two strings, both with length 64, each consisting of lowercase letters, numbers, and spaces: ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB ABAB 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf
The first string allows a short description in the Dutch language, namely "ab 32 times". This description consists of 10 characters. The second string does not have an immediately striking simple description (using the same character set), other than the entire string itself, which consists of 64 characters.
More formally speaking, the complexity of a string is the length of the shortest description of this string in any given universal description language. The sensitivity of the complexity to the choice of the description language is important. It can be shown that the Kolmogorov complexity of any string can not be much greater than the length of this string itself. Strings whose Kolmogorov complexity is small in relation to the size of the string are not considered complex. The notion of Kolmogorov complexity is surprisingly deep and can be used to prove and prove impossibility results related to Gödel's incompleteness and Turing problem.
wiki
