Kolmogorov complexity: Difference between revisions

Revision as of 02:28, 6 April 2002

Revision as of 02:29, 6 April 2002

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 [[Goedels Incompleteness Theorem|Gödel's incompleteness theorem]] and [[halting problem|Turing's halting problem]].

The field was developed by [[Kolmogorov|Andrey Kolmogorov]] and [[Gregory Chaitin]] starting in the late [[1960s]].

To formalize the above definition of complexity, one has to specify exactly what types of programs are allowed.