Content deleted Content added
m legibility of non-TeX math notation |
phrasing |
||
Line 3:
'''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 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 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
:<math>K_1(s) \le K_2 (s) + c </math>
Here, ''c'' is the length in bits of an interpreter for ''L''<sub>2</sub> written in ''L''<sub>1</sub>.
| |||