Kolmogorov complexity

In algorithmic information theory, the Kolmogorov complexity of an object, such as a string of characters, is defined as the length of the shortest computer program that can generate it, serving as a fundamental measure of computational resources that provides a rigorous mathematical foundation for the concepts of algorithmic randomness, data compression, and the formalization of Occam's razor.

History and Origins

The concept was independently developed by three researchers in the 1960s: Ray Solomonoff in 1960, Andrey Kolmogorov in 1963, and Gregory Chaitin in 1966. Solomonoff initially introduced the idea in the context of algorithmic probability and inductive inference. Kolmogorov published his formulation to define randomness in finite strings, while Chaitin expanded on the theory, linking it deeply to Gödel's incompleteness theorems. Consequently, the concept is also frequently referred to as Kolmogorov-Chaitin complexity, Solomonoff-Kolmogorov-Chaitin complexity, algorithmic complexity, descriptive complexity, or program-size complexity.

Formal Definition

Let $s$ be a string of characters. The Kolmogorov complexity of $s$, denoted as $K(s)$, is the length of the shortest program $p$ that, when run on a universal Turing machine $U$, outputs $s$ and halts. Mathematically, this is expressed as $K(s) = \min \{ |p| : U(p) = s \}$, where $|p|$ represents the length of the program in bits. If a string can be generated by a program significantly shorter than the string itself, it is considered to possess low Kolmogorov complexity. Conversely, if the shortest program to generate a string is roughly the same length as the string (e.g., a program that simply prints the string verbatim), the string is said to have high complexity.

Invariance Theorem

A fundamental question arises regarding the choice of the universal Turing machine or programming language used to measure the program's length. The Invariance Theorem addresses this by stating that the choice of the universal machine only affects the complexity by an additive constant. For any two universal Turing machines $U_1$ and $U_2$, there exists a constant $c$ (which depends only on $U_1$ and $U_2$, not on the string $s$) such that $|K_1(s) - K_2(s)| \le c$ for all strings $s$. This constant represents the length of an interpreter program that allows one machine to simulate the other. Therefore, for sufficiently long strings, the choice of the reference machine becomes negligible, making Kolmogorov complexity an asymptotically robust measure.

Incomputability

Despite its elegant definition, Kolmogorov complexity is uncomputable. There is no general algorithm that can take a string $s$ as input and output its exact Kolmogorov complexity $K(s)$. This result is closely related to the halting problem and the Berry paradox. If such an algorithm existed, one could write a program that searches for the first string with a complexity greater than the length of the program itself, leading to a logical contradiction. While $K(s)$ cannot be computed exactly, it can be approximated from above using data compression algorithms, though these approximations may not reach the true theoretical minimum.

Algorithmic Randomness and Compression

Kolmogorov complexity provides a formal definition of randomness for individual finite strings. A string is considered algorithmically random if its Kolmogorov complexity is approximately equal to its length. Such strings are incompressible; no algorithm can represent them more succinctly than simply listing their contents. This establishes a profound link between information theory and data compression: the optimal compression of a string is bounded by its Kolmogorov complexity. By a simple counting argument, most strings of a given length are incompressible, as there are far fewer short programs than there are long strings.

Chain Rule and Properties

The theory includes several important mathematical properties, most notably the chain rule for Kolmogorov complexity. The chain rule states that the complexity of a pair of strings $(X, Y)$ is equal to the complexity of $X$ plus the conditional complexity of $Y$ given $X$, up to a logarithmic term: $K(X, Y) = K(X) + K(Y|X) + O(\log K(X))$. Here, $K(Y|X)$ is the length of the shortest program that produces $Y$ when $X$ is provided as an auxiliary input. This rule mirrors the chain rule in Shannon's information theory but includes the logarithmic overhead required to separate the programs.

Applications and Philosophical Implications

Kolmogorov complexity has far-reaching implications across computer science, mathematics, and philosophy. In machine learning and statistics, it forms the theoretical basis for the Minimum Description Length (MDL) principle, which posits that the best hypothesis for a given set of data is the one that minimizes the sum of the length of the hypothesis and the length of the data encoded using that hypothesis. Philosophically, it provides a rigorous mathematical formulation of Occam's razor, favoring simpler explanations (shorter programs) over complex ones. Furthermore, Gregory Chaitin used algorithmic complexity to prove an information-theoretic version of Gödel's incompleteness theorem, demonstrating that in any sufficiently powerful formal axiomatic system, there is a strict limit to the complexity of strings whose randomness can be formally proven.