Kolmogorov complexity: Difference between revisions

Revision as of 17:30, 18 January 2004

Revision as of 02:47, 3 February 2004

Line 1:

'''Algorithmic information theory''' is a field of study which attempts to capture the concept of complexity by 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]], [[Ray Solomonoff]] and [[Gregory Chaitin]] starting in the late [[1960s]]. There are several