Kolmogorov Complexity
The length of the shortest program that outputs a string — making "random" mean "incompressible."
Contents
Kolmogorov Complexity
The Kolmogorov complexity K(x) of a string x is the length of the shortest computer program that prints x and halts. It is information measured not as average surprise over a Probability Distribution — the way Entropy does it — but as the intrinsic, algorithmic content of one specific object. A string is simple if it has a short description and complex if it does not.
Compare two 1000-bit strings. The string 010101...01 is trivially described — "print 01 five hundred times" — so its complexity is tiny. A string produced by a thousand fair coin flips almost certainly has no description shorter than itself: the best you can do is "print this exact sequence: …". That second string is algorithmically random.
Order is cheap, randomness is dear
The bars contrast the shortest-description length of strings with increasing disorder — from a constant string (one tiny rule) through a simple repeat and a fractal-like pattern, up to genuine noise whose only description is itself.
The catch: it cannot be computed
Here is the twist that makes Kolmogorov complexity profound rather than merely useful: K(x) is uncomputable. No algorithm can take an arbitrary string and return the length of its shortest program. A short diagonal argument — cousin to the halting problem and the Berry paradox ("the smallest number not describable in fewer than twelve words") — shows that a general K-computing machine leads to contradiction. We can upper-bound K(x) (any program that prints x is a witness; a good compressor's output is one) but never be sure we have found the true minimum.
Where it touches dynamics
Kolmogorov complexity is the bridge between information and Chaos. A chaotic orbit looks random precisely because the bits of its trajectory are incompressible — describing the path to n digits takes roughly n bits of initial condition, which a positive Lyapunov Exponent reveals one bit at a time. The intricate self-similarity of a Fractal, by contrast, is the opposite: enormous visual detail generated by a tiny program, the very signature of low complexity. Algorithmic information theory is where "how random is this?" and "how compressible is this?" become the same question.