Difference between revisions of "Kolmogorov complexity"

From Wiki @ Karl Jones dot com
Jump to: navigation, search
(Created page with "In algorithmic information theory (a subfield of computer science and mathematics), the '''Kolmogorov complexity''' of an object, such as a piece of text, is t...")
 
(See also)
 
Line 12: Line 12:
  
 
* [[Algorithmic information theory]]
 
* [[Algorithmic information theory]]
 +
* [[Berry paradox]]
 +
* [[Code golf]]
 +
* [[Computer science]]
 +
* [[Computation]]
 +
* [[Data compression]]
 +
* [[Demoscene]] - a [[computer art]] discipline centered around the creation of smallest programs that achieve certain effects
 +
* [[Grammar induction]]
 +
* [[Important publications in algorithmic information theory]]
 +
* [[Inductive inference]]
 +
* [[Kolmogorov structure function]]
 +
* [[Levenshtein distance]]
 +
* [[Solomonoff's theory of inductive inference]]
  
 
== External links ==
 
== External links ==

Latest revision as of 05:59, 22 May 2016

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

External links