Kolmogorov complexity

Kolmogorov complexity is an interesting idea from algorithmic information theory, a part of both computer science and mathematics. It helps us understand how complicated something—like a piece of text—really is by finding the shortest computer program that can make it. We pick a programming language to write this program ahead of time.

The idea of Kolmogorov complexity tells us about the computational work 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." 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 explains that some description languages are the best possible. This means that any description written in another language can be changed into a description in the best language, adding only a little extra length. The extra length is a fixed number and does not depend 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 the best language. You can do this by adding a small program that changes the description into the best language.

History and context

Algorithmic information theory is a part of computer science that looks at how complicated strings or data can be.

The idea of Kolmogorov complexity began with a theorem found by Ray Solomonoff in 1960. He talked about it in a report about guessing what comes next in a series. Andrey Kolmogorov later shared similar ideas in 1965. Gregory Chaitin also wrote about this in 1966. The theorem shows that there is a best way to make short codes for any string of information.

Solomonoff used this idea to help guess future parts of a string, while Kolmogorov used it to see how complex or random a string is. Over time, scientists mostly connected this idea to Kolmogorov. There are also other types of Kolmogorov complexity, like one based on special programs created by Leonid Levin in 1974.

Basic results

Kolmogorov complexity measures how hard it is to describe something using a computer program. Imagine 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.

Compression

Compressing a string means finding a shorter way to write it down. It's like making a ZIP file on a computer — the file gets smaller, but we can still open it to see the original.

Most strings are hard to make smaller. 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 simple or complex a piece of information 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. It uses ideas from Bayesian thinking and information theory. This principle has helpful features. It can look at data in many ways, improve over time, and help find true models faster. Later, Wallace and D.L. Dowe showed how this idea relates 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 made smaller by using a 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

Kolmogorov complexity is related to a concept called entropy. Entropy measures how much information is needed to describe something.

For some types of information, as more data is created, the Kolmogorov complexity per piece of data gets very close to the entropy of the source.

There is a theorem that connects Kolmogorov complexity with entropy for binary strings. It shows that the complexity of a string, 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 linked in math.

Halting problem

The Kolmogorov complexity of a string is linked to the halting problem — a big challenge in computer science. If we had a magic tool to know right away if a computer program will stop, we could find the Kolmogorov complexity of any string. We could test every possible program until we find one that makes the string.

But going the other way is not easy. Using Kolmogorov complexity, we can make a special program. This program helps us learn about programs that run for a very long time. This ties into a well-known idea called the Busy Beaver problem. The Busy Beaver problem asks how long a program can run before it stops, using a certain number of steps. Ideas from Kolmogorov complexity help scientists study these tough computing questions.

Main article: Busy Beaver

Implications in biology

Kolmogorov complexity helps us understand patterns in living things. Scientists think that evolution prefers simpler designs because they are easier to develop. For example, many insects have body patterns that show symmetry, like an eight-part design. These patterns 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) ), measures how much information is needed to create one string (x) when we already have another string (y). Imagine 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)) ). This measures how much information is needed to create x when we already know the length of x. It shows 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.

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.