Kolmogorov Complexity

Kolmogorov complexity, also called algorithmic complexity, is a measure within algorithmic information theory of how computationally complex a given object, typically a string of symbols, actually is, defined formally as the length of the shortest possible computer program, written in some fixed reference programming language, that would output the exact string when run. The measure and its underlying theory were developed independently in the 1960s by several researchers, most notably Soviet mathematician Andrey Kolmogorov, who published his own formulation in 1965 and for whom the measure is now named, alongside related earlier foundational work on algorithmic probability by Ray Solomonoff published in 1960 and further independent contributions from Gregory Chaitin. Under this framework, a string is considered effectively random, or incompressible, if its Kolmogorov complexity is close to the string's own length in symbols, meaning no meaningfully shorter description of it exists than simply writing the string out in full, whereas a highly patterned string, such as one made of a single digit repeated many times, has very low Kolmogorov complexity because a short program can easily generate it. A fundamental and somewhat counterintuitive property of Kolmogorov complexity is that it is formally uncomputable: no general algorithm exists that can calculate the exact Kolmogorov complexity of an arbitrary given string.