Kolmogorov complexity

Kolmogorov complexity measures how complex a specific piece of data really is by asking how short the shortest computer program would need to be, in some fixed programming language, to produce that exact data as its output. A string that is highly repetitive or follows a simple pattern can be produced by a very short program, so it has low Kolmogorov complexity, while a string that looks like pure random noise generally cannot be compressed into any shorter description, and so has Kolmogorov complexity close to its own length. The measure is named for Andrey Kolmogorov, who first published on the subject in 1963, and it gives algorithmic information theory a rigorous, language-independent way to talk about randomness and information content, even though it is also known to be impossible to compute exactly for an arbitrary piece of data.