While Shannon’s information theory revolutionized telecommunications, it harbored an inherent philosophical limitation: it measured information strictly with respect to a prior probability distribution over an ensemble of messages. Shannon could tell you the average information generated by an ensemble of binary sequences, but he could not quantify the intrinsic information contained within a single, isolated string such as the first billion digits of $pi$ versus a string of coin flips. In the 1960s, Andrey Kolmogorov, Ray Solomonoff, and Gregory Chaitin independently solved this dilemma by founding Algorithmic Information Theory (AIT), defining the complexity of an object as the length of the shortest computer program capable of generating it on a universal Turing machine.
1. The Definition of Kolmogorov Complexity
Let $U$ be a Universal Turing Machine (UTM). The Kolmogorov complexity (or algorithmic complexity) $K_U(s)$ of a finite binary string $s in {0, 1}^*$ with respect to $U$ is the length in bits of the shortest program $p$ that, when executed on $U$, halts and outputs string $s$:
[
K_U(s) = min_{p in {0, 1}^*} { |p| : U(p) = s }
]
If no such program exists, $K_U(s) = infty$. Because a program can always simply hardcode the print statement of the literal string $s$ ($text{“print } stext{“}$), the complexity of any string is upper-bounded by its length plus a machine-specific constant:
[
K_U(s) le |s| + c_U
]
2. The Invariance Theorem: Universality Across Architectures
Does the choice of programming language or reference machine $U$ distort the complexity measure? What if we choose Python versus a Post-Turing machine?
The cornerstone of AIT is the Invariance Theorem (Kolmogorov, Solomonoff, 1965). Let $U_1$ and $U_2$ be any two universal Turing machines. Then for every binary string $s$:
[
|K_{U_1}(s) – K_{U_2}(s)| le c_{12}
]
where $c_{12}$ is a fixed constant independent of $s$. The constant $c_{12}$ is simply the finite length of the compiler or interpreter program written for machine $U_1$ that simulates machine $U_2$. As the string length $|s| to infty$, this constant overhead becomes negligible, proving that Kolmogorov complexity is an objective, machine-independent property of mathematical objects.
3. Algorithmic Incompressibility and True Randomness
AIT provides the first rigorous, non-circular mathematical definition of randomness. In classical probability, one cannot say a single outcome (e.g., $1010101010$) is random; only the generating coin-flip process is called random. Kolmogorov inverted this paradigm: a string is random if and only if it contains zero internal patterns or computational redundancies.
A string $s$ of length $n$ is defined to be algorithmically incompressible (c-incompressible) if:
[
K(s) ge n – c
]
for some small integer constant $c$.
The Abundance of Incompressible Strings
How many strings are random? Consider all binary strings of length $n$, of which there are $2^n$. The total number of available programs of length strictly less than $n – c$ is given by the geometric series:
[
sum_{k=0}^{n-c-1} 2^k = 2^{n-c} – 1
]
Because each program can output at most one string, at most $2^{n-c} – 1$ strings can be produced by programs shorter than $n – c$. Therefore, the fraction of strings of length $n$ that are incompressible is:
[
text{Fraction Random} ge frac{2^n – (2^{n-c} – 1)}{2^n} > 1 – 2^{-c}
]
For $c = 10$, more than $99.9%$ of all binary strings are strictly incompressible! Vast algorithmic randomness is the overwhelming mathematical norm, while structured strings are vanishingly rare anomalies.
4. The Uncomputability of Kolmogorov Complexity
Can a software compiler compute $K(s)$? Kolmogorov proved that $K(s)$ is strictly uncomputable. Suppose there existed a computer function `kolmogorov(s)` that takes any string $s$ and returns the integer $K(s)$. We could then write the following paradoxical program:
find_paradoxical_string(n):
for each binary string s in lexicographical order:
if kolmogorov(s) > n:
return s
This program finds the first string $s^*$ whose complexity exceeds $n$. The length of this program itself is bounded by $log_2(n) + c_{prog}$, because it only requires specifying the integer $n$. But running this program outputs $s^*$, which implies:
[
K(s^*) le log_2(n) + c_{prog}
]
However, by definition of the algorithm, $s^*$ was chosen specifically such that $K(s^*) > n$. For sufficiently large $n$, we obtain the blatant contradiction:
[
n < K(s^*) le log_2(n) + c_{prog}
]
This contradiction—a modern algorithmic formulation of the Berry Paradox—proves that no universal algorithm can compute the Kolmogorov complexity of arbitrary strings. AIT establishes an unbreakable bridge between information theory and the absolute limits of mathematical reason.
