Content deleted Content added
less than --> fewer than |
added Levin, Solomonoff, Schmidhuber, Li and Vitanyi |
||
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).
To formalize the above definition of complexity, one has to specify exactly what types of programs are allowed. Fortunately, it doesn't really matter: one could take a particular notation for [[Turing machine|Turing machines]], or [[Lisp programming language|LISP]] programs, or [[Pascal programming language|Pascal]] programs, or [[Java virtual machine]] bytecode. If we agree to measure the lengths of all objects consistently in [[bit|bits]], then the resulting notions of complexity will only differ by a constant factor: if ''I''<sub>1</sub>(''s'') and ''I''<sub>2</sub>(''s'') are the complexitites of the string ''s'' according to two different programming languages ''L''<sub>1</sub> and ''L''<sub>2</sub>, then there are constants ''C'' and ''D'' (which only depend on the languages chosen, but not on ''s'') such that
Line 27 ⟶ 29:
'''See also:'''
* [http://www.cs.umaine.edu/~chaitin/ Chaitin's online publications]
* [http://www.idsia.ch/~juergen/ray.html Solomonoff's IDSIA page]
* [http://www.idsia.ch/~juergen/kolmogorov.html Schmidhuber's generalizations of algorithmic information]
* [http://homepages.cwi.nl/~paulv/kolmogorov.html Li & Vitanyi's textbook]
| |||