Kolmogorov complexity: Difference between revisions

Revision as of 14:56, 20 November 2003

Revision as of 18:05, 11 December 2003

Line 1:

'''Algorithmic information theory''' is a field of study which attempts to capture the concept of complexity using tools from theoretical computer science. The chief idea is to define the complexity (or '''Kolmogorov complexity''') of a [[string]] as the length of the shortest program which, when run without any input, outputs that string. Strings that can be produced by short programs are considered to be not very complex. This notion is surprisingly deep and can be used to state and prove impossibility results akin to [[Gödel's incompleteness theorem]] and [[halting problem|Turing's halting problem]].

The field was developed by [[Andrey Kolmogorov]] and, [[Ray Solomonoff]] and [[Gregory Chaitin]] starting in the late [[1960s]]. There are several

variants of Kolmogorov complexity or algorithmic information. The most widely used one is based on self-delimiting programs and is due to [[Leonid Levin]] (1974).