Kolmogorov complexity

Kolmogorov complexity is a fascinating idea from algorithmic information theory, a part of both computer science and mathematics. It helps us understand how complicated an object—like a piece of text—really is by looking at the shortest computer program that can create it. This shortest program is written in a specific programming language that we decide on ahead of time.

The concept of Kolmogorov complexity tells us about the computational effort needed to describe something exactly. It’s named after Andrey Kolmogorov, who first wrote about it in 1963. This idea connects to many important thoughts in math and computer science, like Cantor's diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem.

One interesting thing about Kolmogorov complexity is that it shows us some things we can’t know for sure. For example, there’s no single program that can perfectly measure the complexity of every possible text. This is similar to how some math problems, like Turing’s halting problem, have no easy answers.

Definition

Imagine you have two strings of letters and numbers. One string looks like "abababababababababababababababab" — it repeats "ab" many times. You can describe this string simply by saying "write 'ab' 16 times," which is much shorter than writing out the whole string. The other string, "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7," doesn’t have an easy short description. You usually have to write the whole thing out.

Kolmogorov complexity measures how easy it is to describe something. It looks for the shortest computer program that can create the string. The string with the repeating pattern has low Kolmogorov complexity because it’s easy to describe. The more random-looking string has high Kolmogorov complexity because there’s no simpler way to write it down than just listing all the characters.

Kolmogorov complexity can be used for many things, not just strings of letters. It helps us understand how much information is really needed to create something, whether it’s a piece of text, a picture, or even a math problem. The idea was first shared by Andrey Kolmogorov in 1963 and has grown into a big part of computer science and math.

Invariance theorem

The invariance theorem tells us that some description languages are optimal. This means that any description in another language can be turned into a description in the optimal language with just a little extra length. The extra length is a constant and does not change based on what you are describing.

To understand this, imagine a description with two parts. The first part describes another language, and the second part describes the object using that language. The theorem shows that any description in one language can be made almost as short as in an optimal language, with only a small, fixed amount of extra length. This is because you can include a small program that translates the description into the optimal language.

History and context

Algorithmic information theory is a part of computer science that studies how complex strings or data structures can be.

The idea of Kolmogorov complexity started with a theorem discovered by Ray Solomonoff in 1960. He described it in a report about inductive inference. Andrey Kolmogorov later published similar work independently in 1965. Gregory Chaitin also presented this idea in a journal in 1966. The theorem explains that there is an optimal way to decode strings from their descriptions, meaning there is a best method to make the shortest possible codes for any string.

Solomonoff used this idea to create a way to predict future parts of a string, while Kolmogorov used it to measure how complex or random a string is. Over time, the scientific community mostly linked this concept to Kolmogorov. There are also other versions of Kolmogorov complexity, like one based on self-delimiting programs introduced by Leonid Levin in 1974.

Basic results

Kolmogorov complexity measures how hard it is to describe something using a computer program. Think of it like this: if you can write a very short program that creates a big picture or a long piece of text, then that picture or text has low Kolmogorov complexity. If you need a very long program to create something, it has high Kolmogorov complexity.

There are important rules about how Kolmogorov complexity works. For example, describing two things together is usually not much harder than describing each one separately. Also, it's impossible to write a program that can find the Kolmogorov complexity of any random piece of text—this would require solving problems that computers can never solve, like knowing whether a program will ever finish running.

Compression

Compressing a string means finding a shorter way to represent it. We can think of this like creating a ZIP file on a computer — the file gets smaller, but we can still unpack it back to the original.

Most strings are hard to compress. For example, if you have a string of bits like 01011001, there might not be a much shorter way to describe it. This idea helps us understand how complex or simple a piece of information really is.

Chaitin's incompleteness theorem

There is a limit to what we can prove about how complex a piece of information is. Imagine trying to write a very short computer program that creates a specific piece of text. Sometimes, we can't prove that no shorter program exists to create that text, especially if the text is very complex.

This idea comes from a special kind of math used to study how we can describe information. It shows that for some pieces of information, no matter how powerful our math rules are, we can't always prove just how complex they are. This is similar to how some puzzles can’t be solved with certain rules.

Minimum message length

Main article: Minimum message length

The minimum message length principle was created by C.S. Wallace and D.M. Boulton in 1968. This principle uses Bayesian ideas and information theory. It has useful properties like being able to handle different ways of looking at data, getting better over time, and finding true models quickly. Later, Wallace and D.L. Dowe showed how this idea connects to Kolmogorov complexity.

Kolmogorov randomness

See also: Algorithmically random sequence

Kolmogorov randomness describes a string of numbers as random if the shortest computer program that can create that string is almost as long as the string itself. This means the string cannot be "compressed" into a smaller program. For example, a random string of bits has no shorter way to describe it than writing out the entire string.

This idea can also apply to very long sequences. These sequences are considered random if, as they grow longer, their shortest description keeps getting longer at a steady rate. This helps us understand what it means for information to be truly random.

Relation to entropy

The Kolmogorov complexity of something is connected to a concept called entropy, which measures how much information is needed to describe it. For certain types of information sources, as more and more data is produced, the Kolmogorov complexity per unit of data gets very close to the entropy of the source.

There is a theorem that links Kolmogorov complexity with entropy for binary strings. It shows that the complexity of a string, when divided by its length, is bounded by a formula involving the binary entropy function and some small extra terms. This helps us understand how randomness and information are related in mathematical terms.

Halting problem

The Kolmogorov complexity of a string is closely tied to the halting problem — a classic challenge in computer science. If we had a special tool to instantly know whether any computer program will stop running, we could calculate the Kolmogorov complexity of any string by testing every possible program until one produces the string.

However, the reverse isn’t straightforward. Using Kolmogorov complexity, we can create a special kind of program that helps us understand the behavior of programs that run for the longest time possible. This connects to a famous concept called the Busy Beaver problem, which asks about the longest a program can run before it stops, given a certain number of steps. The ideas from Kolmogorov complexity help researchers explore these difficult questions in computing.

Main article: Busy Beaver

Implications in biology

Kolmogorov complexity helps us understand patterns in living things. Scientists think that evolution favors simpler solutions because they are easier to develop. For example, many insects have body patterns that show symmetry, like an eight-part design, which can work well and need less complexity to form through natural processes. This idea connects how living things evolve with the concept of finding the shortest "program" to create a function.

Conditional versions

The conditional Kolmogorov complexity of two strings, written as ( K(x|y) ), is a way to measure how much information is needed to create one string (x) when we already have another string (y). Think of it like this: if you already know part of a puzzle (y), you might need fewer clues to figure out the rest of the puzzle (x).

There is also a special version called length-conditional complexity, written as ( K(x|L(x)) ), which measures how much information is needed to create x when we already know the length of x. This helps us understand how knowing just the size of something can make it easier to describe.

Time-bounded complexity

Time-bounded Kolmogorov complexity is a special version of Kolmogorov complexity. In this version, we only look at programs that can run within a certain number of steps. Researchers think that finding an efficient way to measure this type of complexity might help answer big questions in computer science, like whether certain functions can be reversed easily or not.

This idea connects to the study of one-way functions, which are functions that are easy to compute in one direction but very hard to reverse.