Kolmogorov complexity (nonfiction)
In Algorithmic information theory (nonfiction), the Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object.
It is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy.
Andrey Kolmogorov first published on the subject in 1963.
The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to Cantor's diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem. In particular, for almost all objects, it is not possible to compute even a lower bound for its Kolmogorov complexity, let alone its exact value.
See also
- Algorithmic information theory (nonfiction) - the study of the irreducible information content of strings (or other data structures). Because most mathematical objects can be described in terms of strings, or as the limit of a sequence of strings, it can be used to study a wide variety of mathematical objects, including integers.
- Andrey Kolmogorov (nonfiction) - Andrey Nikolaevich Kolmogorov (25 April 1903 – 20 October 1987) was a Soviet mathematician who made significant contributions to the mathematics of probability theory, topology, intuitionistic logic, turbulence, classical mechanics, algorithmic information theory, and computational complexity.
- Andrey Kolmogorov @ Wikipedia
- Kolmogorov complexity @ Wikipedia