Kolmogorov complexity

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, - wikipedia

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.

caption

Written on February 6, 2023, Last update on February 8, 2023
math mental-model