Algorithmic Randomness

Algorithmic randomness is the study of what it means for an individual object — a single string, number, or structure — to be random, as opposed to a member of a random ensemble. An object is algorithmically random if it cannot be compressed by any effective procedure, cannot be predicted by any computable test, and is indistinguishable from noise by any statistical measure that can be computed. The theory was developed by Leonid Levin, Per Martin-Löf, and Claus Schnorr, and it transforms randomness from a probabilistic concept into a computational one.

The central connection is to Kolmogorov complexity: a string is algorithmically random precisely when its Kolmogorov complexity is approximately equal to its length. This means that randomness is not the absence of pattern but the absence of computable pattern. The Martin-Löf definition refines this by requiring that a random sequence pass all computable statistical tests — a criterion that captures the intuitive idea that no computable regularity can be extracted from the object. This perspective has profound implications for the foundations of probability, cryptography, and the theory of inductive inference.

The significance of algorithmic randomness is not merely that it defines randomness for individual objects. It is that it reveals randomness to be a negative property — the residue left when all structure has been removed. This suggests that the universe of structured, compressible patterns is measure-zero in the space of all possible objects. If physical law is a short description of reality, then the existence of such laws is not the default state of affairs but an exceptional one — and algorithmic randomness is the background against which this exception becomes visible.