CONCEPT
Kolmogorov Complexity
The amount of information in an object is the length of the shortest program that produces it—
Kolmogorov’s 1965 definition that made information intrinsic to things rather than relational to ensembles, and that formally identifies compression with comprehension: to understand is to compress, and the depth of understanding is measured in bits saved.
Before Kolmogorov, information was a statistical concept: it described the average surprise in a stream of messages drawn from a known distribution. Claude Shannon’s magnificent apparatus could tell you the entropy of a source but could not say anything about a single object considered alone, because a lone message has no distribution.
Andrey Kolmogorov’s 1965 paper made the measure intrinsic. The complexity of a string, on his definition, is the length in bits of the shortest program that outputs it on a universal computer. A string of a million zeros has low complexity—a short program produces it. A genuinely random string of a million bits has complexity approaching a million—no program shorter than itself generates it. This relocates information from channels to things, from distributions to objects, from the statistical ensemble to the individual instance. Every learning machine is, in the