Kolmogorov complexity

Imagine you want to share a secret code.

Some codes are very short to say. You might say, "Write AB sixteen times." That is a quick way!

Other codes are much longer. You might have to say every single letter one by one. This takes a lot more time.

Math experts look for the shortest way to describe things. They call this complexity. It is like finding the smallest set of rules. A small program can make a big, pretty picture. This helps us see how much information is inside. It is a way to measure how hard something is to describe.

Imagine you want to tell a friend how to draw a pattern.

You could list every single dot and color. This would take a very long time. Or, you could give them a simple rule. A small rule can make a huge, beautiful picture.

This idea is called Kolmogorov complexity.

In math, complexity is the length of the shortest program. A program is a set of instructions for a computer. We want to find the shortest way to describe an object. For example, saying "write AB sixteen times" is very short. But writing out a long string of random letters is much longer. The first string has less complexity.

Andrey Kolmogorov published his ideas in 1963. He wanted to study randomness and information. Other thinkers like Ray Solomonoff and Gregory Chaitin also worked on this. They found that there is an optimal way to describe things. This means one way is as good as any other. It might just be a little bit different in length. This helps us understand how much information is truly inside an object.

Imagine you want to tell a friend how to draw a beautiful, swirling picture.

You could try to list every single tiny dot and color one by one. This would take a huge amount of time and many pages of notes. Instead, you could give them a simple mathematical rule to follow. A very small set of instructions can create a massive, complex image. This idea is the heart of Kolmogorov complexity. It measures how much information is truly needed to describe something.

In math, we look for the shortest possible computer program that can make an object. A program is just a list of instructions for a computer to follow. If you have a string of letters like "abababab", you can just say "write ab four times." This short instruction is much smaller than writing the whole string out. However, a string of random letters has no simple pattern. To describe it, you must write out every single character. The random string has much higher complexity because its shortest description is very long.

This field of study is called algorithmic information theory. It looks at how much work a computer needs to specify an object. Many people helped build these ideas over many years. Ray Solomonoff first published important work on this in 1960. He was looking at how to make predictions using math. Later, Andrey Kolmogorov published his own famous work in 1963. He was interested in how randomness works in a sequence. Gregory Chaitin also added to these ideas in the late 1960s.

There are different ways to measure this complexity. One way is called plain complexity, which is very intuitive to understand. Another way is called prefix-free complexity, which is easier for mathematicians to study. Researchers also use a special rule called the invariance theorem. This theorem says that different computer languages will give similar results. The length of the shortest description might change slightly between languages. However, it will only change by a small, constant amount. This means the core idea of complexity stays the same no matter the language.

We can see these ideas in the world around us every day. Think about how computers shrink large files to save space. This process uses patterns to make descriptions much shorter. A simple rule can describe a huge file that would otherwise be too big. Even a complex fractal image can be made from a tiny bit of code. This shows us that patterns are a powerful way to store information. Mathematics helps us find the most efficient way to talk about the world.

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.