View source for Kolmogorov complexity

In [[algorithmic information theory]] (a subfield of [[computer science]] and [[mathematics]]), 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.

== Description ==

It is a measure of the [[computational resources]] needed to specify the object, and is also known as descriptive complexity, Kolmogorov–Chaitin complexity, algorithmic entropy, or program-size complexity.

It is named after [[Andrey Kolmogorov]], who 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]].

== See also ==

* [[Algorithmic information theory]]

== External links ==

* [https://en.wikipedia.org/wiki/Kolmogorov_complexity Kolmogorov complexity] @ Wikipedia


[[Category:Computer science]]
[[Category:Mathematics]]