Kolmogorov Complexity (Minimum Description Length)

Kolmogorov complexity measures the shortest generating program for an object on a specified universal machine and is uncomputable in general. MDL is a related model-selection approach comparing the encoding of a model plus the data given that model.

Kolmogorov complexity is the length of a shortest program that produces a particular object on a specified universal computing system. A regular string may have a short generating program; most sufficiently long strings cannot be substantially compressed. The exact complexity is uncomputable in general, and a finite random draw can still happen to produce a simple pattern.

Minimum description length is a related practical principle for comparing models through the total cost of encoding the model and the data given it. It is not identical to computing Kolmogorov complexity. The useful tradeoff is between a complicated model that memorizes observations and a simpler model that leaves many exceptions to encode. A short slogan that omits important data is not a better explanation merely because it uses fewer words.

When to use it

When studying algorithmic information or comparing statistical representations that trade model complexity against residual data.

How it can help

Compare complete model-and-data descriptions under explicit coding rules. Include exceptions and parameter costs rather than rewarding a short explanation that discards inconvenient observations.