Kolmogorov complexity (nonfiction): Difference between revisions
Jump to navigation
Jump to search
(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 |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
In | 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 (nonfiction)|Andrey Kolmogorov]] first published on the subject in 1963. | [[Andrey Kolmogorov (nonfiction)|Andrey Kolmogorov]] first published on the subject in 1963. | ||
| Line 6: | Line 8: | ||
== See also == | == 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 (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 | ||
[[Category:Nonfiction (nonfiction)]] | |||
[[Category:Complexity (nonfiction)]] | |||
[[Category:Mathematics (nonfiction)]] | |||
[[Category:Andrey Kolmogorov (nonfiction)]] | |||
[[Category:To do (nonfiction)]] | |||
Latest revision as of 10:08, 6 September 2023
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