 Kolmogorov complexity

Kolmogorov complexity measures the length of a shortest effective description of an object. Fixing an optimal description machine gives an invariant quantity up to an additive machine-dependent constant. Plain Kolmogorov complexity is especially convenient for counting descriptions shorter than a binary string.

Kolmogorov complexity, named after the Russian mathematician Andrey Kolmogorov, is a concept in algorithmic information theory that quantifies the complexity of a string or object in terms of the length of the shortest possible description or program that can generate that string using a fixed computational model (usually a Turing machine).