Kolmogorov Complexity

A description-based measure of information

Claude Shannon's Information Theory describes compression limits from the statistical properties of a data source. Shannon's entropy gives the average information per symbol and sets a theoretical limit for compressing a long message from that source. This measure concerns averages and requires a probabilistic model of the data source.

A single object can also be analyzed without building a model of average frequencies. Examples include the first chapter of Moby Dick as a specific string of characters and one digital photograph of a cat. These questions lead to Algorithmic Information Theory and its central concept, Kolmogorov Complexity. In this view, the object is one fixed representation, and the result depends on how it is described.

Defining Kolmogorov Complexity

Developed independently in the 1960s by Andrey Kolmogorov, Ray Solomonoff, and Gregory Chaitin, the idea identifies an object's complexity with the length of its shortest description. For digital data, such a description can be a computer program. The value depends on the selected machine, while the invariance theorem bounds that dependence by a fixed overhead.

Thus, the formal definition is as follows:

Elements of the definition

The definition can be divided into the following parts:

• A String $s$:In this context, a "string" can be any digital object. It can be a sentence, a binary image file, the bit sequence of an executable program, or the first trillion digits of pi. It is the object whose complexity is being measured. Each object has a finite input representation.
• A Computer Program $p$: This is a program executed by a fixed universal machine. Its length is measured in bits of the program encoding, usually with a self-delimiting encoding. Source-code character counts depend on the language and do not define $K(s)$.
• Outputs the String $s$: When executed, program $p$ must generate $s$ as its output. A fixed convention for separating a program from its data makes the description length well-defined.
• And Then Halts: The program must finish its computation after generating the output. This condition connects the definition to computability theory and the Halting Problem.
• The Shortest Program: Many programs can generate a given string. A program can contain data and a lookup function, or calculate the string algorithmically. Complexity is the length of the shortest program among these possibilities.

Language choice and the invariance theorem

One might wonder if the complexity of a string depends on the programming language chosen. A program written in Python might be shorter than an equivalent program in Assembly language. Does this mean the string is "simpler" in Python?

The invariance theorem describes this dependence on the language. For any two universal programming languages L1 and L2, the complexity difference for a string $s$ is bounded by a constant depending only on those languages. It can be written as $|K_{L1}(s)-K_{L2}(s)| \le c$, where $c$ does not depend on $s$. The constant can include the translator and the input-output convention. A translator from one language to the other has fixed length, so its overhead does not depend on $s$. Exact values of $K(s)$ can differ, but their difference remains bounded. Theoretical analyses therefore use one fixed description machine.

Examples of descriptive complexity

These examples show the difference between a string's appearance and the length of its algorithmic description.

Example 1: The simple, repetitive string

Consider an ordered string, $s_1$, consisting of the character 'A' repeated 1,000 times.

It can be generated by a program that contains the entire string:

A literal representation of 1,000 letters requires about 1,000 data characters and does not shorten the description. A shorter program can use a loop:

For the fixed value 1,000, the loop is short compared with the literal representation, so $s_1$ has low Kolmogorov complexity, $K(s_1) \ll 1000$. For the family $A^n$, the description must also encode $n$, so its length includes the bits needed to represent the chosen value of $n$. The shared rule still gives a short algorithmic description, and the cost of encoding the counter grows much more slowly than the literal string.

Example 2: A high-complexity string

Consider a string $s_2$with the same length of 1,000 characters, generated by 1,000 flips of a fair coin, for example 'HTTHHTH...'.

A single random outcome can lack a short rule. A typical result of 1,000 flips has high complexity with high probability, but the generation process alone does not prove that a particular string is incompressible. If no short description is found, the direct description is the string itself:

For a typical outcome, the shortest program has a length close to the string length, so $K(s_2) \approx 1000$ is a useful illustration. A string whose complexity is close to its length is called algorithmically random or incompressible relative to the selected machine. It has no shorter description in that model. Individual outcomes can contain accidental regularities, so the classification concerns the particular string and the selected tolerance.

Example 3: Digits of Pi

Consider a third string, $s_3$, containing the first one million digits of the mathematical constant Pi.

In computed samples, the digits appear with frequencies close to equal and show no simple repeating patterns. This appearance does not prove an equal distribution for the full expansion. For a chosen model, a statistical measure such as Shannon entropy can indicate high information content, similar to a random string.

Pi is a precisely defined and computable mathematical constant. Algorithms such as the Chudnovsky algorithm and the Bailey-Borwein-Plouffe formula can calculate its digits. A program implementing one of them can be much shorter than the digit list.

The program contains the algorithm and a parameter $n$, so its description does not grow in proportion to the number of digits. For one million digits, an implementation may be a few kilobytes, depending on the language and machine model, which is much shorter than one million characters. The parameter specifying the requested number of digits must also be encoded. Thus $s_3$ has a short description relative to its length despite its random appearance.

Kolmogorov complexity and Shannon entropy

The two measures describe different properties of data.

The digits of Pi illustrate the difference. Shannon entropy describes digit statistics under a chosen model, while Kolmogorov complexity describes the length of a program that generates a specific prefix. Entropy depends on the source distribution, whereas $K(s)$ concerns one outcome. Kolmogorov complexity supplies another criterion, but its exact value is uncomputable.

Uncomputability of the complexity

A compressor cannot find the shortest program for every file. The Kolmogorov complexity of a string is uncomputable.

This follows from the Halting Problem, a result in computability theory associated with Alan Turing. No general algorithm can inspect any program and input and determine whether the program will halt or run forever. Searching for the shortest program would require exactly these decisions for programs that have not finished.

To estimate $K(s)$, we can generate programs from the shortest ones and check their outputs. A program that produces $s$ and halts gives an upper bound for $K(s)$. If another program runs for a minute, an hour, or a year, we cannot know whether it will finish or remain in a loop. Without resolving the Halting Problem, we cannot exclude a shorter program or prove that the description found is optimal.

Practical significance and a theoretical limit

Uncomputability does not remove its role as a reference concept for compression. It states the shortest-description question precisely, even though a practical algorithm can only find an approximation. A found program proves an upper bound for the complexity, while proving that no shorter program exists is the difficult part. This distinction separates a useful compressed representation from a proof of optimality. The machine and encoding convention belong to the definition, so changing either changes the additive constant. Comparisons between coders should include headers and side information required by the decoder.

• Defining the Limit: It provides a theoretical reference for lossless compression. For a fixed decoder, a description containing a file cannot be shorter than $K(s)$ apart from the constant needed to describe that decoder. This sets a limit on possible reductions. A practical compressor can provide an upper bound by presenting one description it has found.
• Guiding Algorithm Design: ZIP, PNG, and FLAC use specific computable techniques such as repeated-string searches and statistical models. They do not search all programs. For a given data set, an algorithm is more effective when it finds a shorter description while preserving correct decoding. The result also contains headers, dictionaries, or model data needed by the decoder, so the full description matters.
• Formalizing Randomness: It gives a formal criterion for algorithmic randomness. A string is algorithmically random when its complexity is close to its length, with the machine-dependent constant taken into account. The concept is used in computability and information analysis.

Kolmogorov Complexity describes an individual object through the length of its shortest program, with values defined up to a constant for a fixed machine. Its uncomputability prevents exact evaluation for every string. Searching for shorter valid descriptions remains a useful reference for lossless compression, because every practical coder selects descriptions from a restricted, computable class of programs.