Kolmogorov complexity (nonfiction): Difference between revisions
(Created page with "In algorithmic information theory, the '''Kolmogorov complexity''' of an object, such as a piece of text, is the length of the shortest computer program (in a predetermined pr...") |
No edit summary |
||
| Line 1: | Line 1: | ||
In algorithmic information theory, 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. | In algorithmic information theory, 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 (nonfiction)|Andrey Kolmogorov]] first published on the subject in 1963. | [[Andrey Kolmogorov (nonfiction)|Andrey Kolmogorov]] first published on the subject in 1963. | ||
| Line 8: | Line 10: | ||
* [[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 (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. | ||
* [https://en.wikipedia.org/wiki/Andrey_Kolmogorov Andrey Kolmogorov] @ Wikipedia | |||
* [https://en.wikipedia.org/wiki/Kolmogorov_complexity Kolmogorov complexity] @ Wikipedia | * [https://en.wikipedia.org/wiki/Kolmogorov_complexity Kolmogorov complexity] @ Wikipedia | ||
Revision as of 20:33, 20 October 2019
In algorithmic information theory, 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
- 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