home | alphabetical index | |||||

## Algorithmic information theoryAlgorithmic 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 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 machines, or LISP programs, or Pascal programs, or Java virtual machine bytecode. If we agree to measure the lengths of all objects consistently in bits, then the resulting notions of complexity will only differ by a constant factor: if D is the length of an interpreter for L_{2} written in L_{1}, and C describes the overhead of storing programs written in L_{2} as part of programs in L_{1}.
In the following, we will fix one definition and simply write
The first surprising result is that
It is however straightforward to compute upper bounds for
The next important result is about the randomness of strings. Most strings are complex in the sense that they cannot be significantly compressed: *I will attach a prize of $5,000 to anyone who successfully meets this challenge. First, the contestant will tell me HOW LONG of a data file to generate. Second, I will generate the data file, and send it to the contestant. Last, the contestant will send me a decompressor and a compressed file, which will together total in size less than the original data file, and which will be able to restore the compressed file to the original state.**With this offer, you can tune your algorithm to my data. You tell me the parameters of size in advance. All I get to do is arrange the bits within my file according to the dictates of my whim. As a processing fee, I will require an advance deposit of $100 from any contestant. This deposit is 100% refundable if you meet the challenge.*
L (which only depends on the particular axiomatic system and the choice of definition of complexity) such that there is no string s for which the statement
Similar ideas are used to prove the properties of Chaitin's constant The minimum message length principle of statistical and inductive inference and machine learning was independently developed by C.S. Wallace and D.M. Boulton in 1968. MML is Bayesian (it incorporates prior beliefs) and information-theoretic. It has the desirable properties of statistical invariance (the inference transforms with a re-parameterisation, such as from polar co-ordinates to Cartesian co-ordinates), statistical consistency (even for very hard problems, MML will converge to any underlying model) and efficiency (the MML model will converge to any true underlying model about as quickly as is possible). C.S. Wallace and D.L. Dowe showed a formal connection between MML and algorithmic information theory (or Kolmogorov complexity) in 1999. ## External links- Chaitin's online publications
- Solomonoff's IDSIA page
- Schmidhuber's generalizations of algorithmic information
- Li & Vitanyi's textbook
- Minimum Message Length and Kolmogorov Complexity (by C.S. Wallace and D.L. Dowe, Computer Journal, Vol. 42, No. 4, 1999).
- David Dowe's Minimum Message Length (MML) and Occam's razor pages.
| |||||

copyright © 2004 FactsAbout.com |