Kolmogorov complexity

Kolmogorov complexity is a fundamental concept in algorithmic information theory. It provides a way to measure the amount of information contained within an object, such as a string of text or a digital image. Instead of measuring size in bits or bytes, Kolmogorov complexity measures the length of the shortest possible computer program that can produce that object as output. This value represents the absolute limit of how much an object can be compressed. It tells us how much computational resource is required to specify an object exactly.

To understand how this works, imagine comparing two different strings of 32 characters. The first string might be "abababababababababababababababab." You can describe this string very simply by saying "write ab 16 times." This instruction is only 17 characters long. The second string might be a random sequence like "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7." There is no pattern to exploit here. To describe it, you must write out the entire string, which takes 38 characters. Because the first string has a much shorter description, it has lower Kolmogorov complexity.

Mathematicians define this complexity using a description language, which is often a computer programming language like Java or Lisp. If a program $P$ produces a string $x$, then $P$ is a valid description of $x$. The complexity, denoted as $K(s)$, is the length of the absolute shortest description possible. There are two main ways to define this. The first is called plain complexity, which is the most intuitive version. The second is prefix-free complexity, which uses a special type of code where no valid program is a prefix of another. This second version is often easier for researchers to use in formal mathematical proofs.

This field grew from the work of several brilliant thinkers. Ray Solomonoff published important findings in 1960 regarding algorithmic probability. He wanted to use math to improve how computers make predictions. Andrey Kolmogorov published his own work on the subject in 1963. He was specifically interested in how randomness appears in sequences of data. Gregory Chaitin also contributed significantly to these ideas in the late 1960s. While Solomonoff focused on prediction, Kolmogorov's name became most closely associated with the measure of complexity itself.

A vital part of this theory is the invariance theorem. You might wonder if the complexity of an object changes depending on whether you use Python or C++ to describe it. The invariance theorem states that the choice of language only changes the result by a constant amount. This constant is an overhead cost that depends on the languages themselves, not on the object being described. You can think of this as the size of a translator program. Once you have the translator, the description of the object remains essentially the same across different systems.

We can see the power of this concept in complex visual data. Consider a high-resolution image of a Mandelbrot set fractal.

Storing every single pixel's color might require 23 million bytes of data. However, the entire image can be recreated using a very small computer program. This program only needs the mathematical definition of the set and a few coordinates. Therefore, the Kolmogorov complexity of the image is much lower than its actual file size. Even standard compression like PNG only reduces the file to 1.6 MB, which is still much larger than its true complexity.

Kolmogorov complexity is deeply connected to other major ideas in logic and computer science. It can be used to prove impossibility results similar to Gödel's incompleteness theorem or Turing's halting problem. For example, it is impossible to write a single program that can calculate the exact Kolmogorov complexity for every possible text. This is because no program can return a value significantly larger than its own length. This deep connection shows that the limits of information are tied to the very limits of what computers can calculate.