Applications of algorithmic information theory - davidar/scholarpedia GitHub Wiki
Algorithmic Information Theory, more frequently called Kolmogorov complexity, has a wide range of applications, many of them described in detail by Li and Vitanyi (2008). The range of applications so vast that every such selection cannot be comprehensive or even cover all important items. The applications can use the property that:
- most strings are effectively incompressible, or
- some strings can be effectively compressed, or
- some strings can be effectively compressed but take a lot of effort to do so, or
- different strings can be effectively compressed in various degrees, singly, jointly, or conditionally on one another, and that approximating the Kolmogorov complexity with real-world compressors still gives acceptable, or even very good, results.
A new mathematical proof technique was developed, now known as the incompressibility method. It is based on the fact that most strings (the so-called Martin-Loef random strings, also called Kolmogorov random strings) cannot be effectively compressed. The method and applications are surveyed in detail in Li and Vitanyi (2008), Chapter 6.
The incompressibility of random objects yields a simple but powerful proof technique. The incompressibility method is a general-purpose tool and should be compared with the pigeon-hole principle or the probabilistic method. Whereas the older methods generally show the existence of an object with the required properties, the incompressibility argument shows that almost all objects have the required property. This follows immediately from the fact that the argument is typically used on a Kolmogorov random object. Since such objects are effectively indistinguishable, the proof holds for all such objects. Each class of objects has an abundance of objects that are Kolmogorov random relative to the class.
The incompressibility method has been successfully applied to solve open problems and simplify existing proofs. The method rests on a simple fact: a Kolmogorov random string cannot be compressed. Generally, a proof proceeds by showing that a certain property has to hold for some `typical' instance of a problem. Since `typical' instances are difficult to define and often impossible to construct, a classical proof usually involves all instances of a certain class.
By intention and definition, an individual Kolmogorov random object is a `typical' instance. These are the incompressible objects. Although individual objects cannot be proved to be incompressible in any given finite axiom system, a simple counting argument shows that almost all objects are incompressible. In a typical proof using the incompressibility method, one first chooses a Kolmogorov random object from the class under discussion. This object is incompressible. Then one proves that the desired property holds for this object. The argument invariably says that if the property does not hold, then the object can be compressed. This yields the required contradiction.
Because we are dealing with only one fixed object, the resulting proofs tend to be simple and natural. They are natural in that they supply rigorous analogues for our intuitive reasoning. In many cases a proof using the incompressibility method implies an average-case result since almost all strings are incompressible.
The incompressibility method has been applied in, among others,
- recursion theory to analyse notions of randomness, this line of research is compiled in Downey and Hirschfeldt (2010),
- combinatorics, combinatorial geometry,
- statistics,
- graph theory, expanders,
- Kolmogorov 0-1 Laws, probability theory,
- theory of parallel and distributed computation,
- time and space complexity of computations, language recognition, string matching, Turing machine complexity, computational complexity of tapes, stacks, queues, solving many well-researched open problems of several decades standing,
- sorting algorithms,
- communication complexity,
- routing in computer networks,
- circuit theory,
- formal language and automata theory, parallel computation, lower bound proof techniques.
- physics: thermodynamics; explanation of Maxwell's Demon paradox, quantum information theory.
In the nineteenth century, Chebychev showed that the number of primes less than <math>n</math> grows asymptotically like <math>n/\log n\ .</math> Using the incompressibility method we cannot (yet) prove this statement precisely, but we can come remarkably close with a minimal amount of effort. We first prove, following G.J. Chaitin, that for infinitely many <math>n\ ,</math> the number of primes less than or equal to <math>n</math> is at least <math>\log n/ \log \log n\ .</math> The proof method is as follows. For each <math>n\ ,</math> we construct a description from which <math>n</math> can be effectively retrieved. This description will involve the primes less than <math>n\ .</math> For some <math>n</math> this description must be long, which shall give the desired result.
Assume that <math>p_1 , p_2 , \ldots , p_m</math> is the list of all the primes less than <math>n\ .</math> Then,
- <math></math>
Stimulated by this work, a competitive approach based on compression has been developed to Pearson-Neyman hypothesis testing (null-hypothesis versus alternative hypothesis), tests for randomness of strings generated by random number generators, and lossy compression and denoising via compression.
R. Downey, D. Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag, New York, 2008.
J.J. Rissanen, Information and Complexity in Statistical Modeling, Springer-Verlag, New York, 2007.
Bibliography, http://www.cs.uwaterloo.ca/~mli, http://www.cwi.nl/~paulv
Internal references
- Marcus Hutter (2007) Algorithmic information theory. Scholarpedia, 2(3):2519.
- Marcus Hutter, Shane Legg, Paul M.B. Vitanyi (2007) Algorithmic probability. Scholarpedia, 2(8):2572.
- Rodney G. Downey and Jan Reimann (2007) Algorithmic randomness. Scholarpedia, 2(10):2574.
- Paul M.B. Vitanyi (2007) Andrey Nikolaevich Kolmogorov. Scholarpedia, 2(2):2798.
- Zhong-Lin Lu and Barbara Anne Dosher (2007) Cognitive psychology. Scholarpedia, 2(8):2769.
- Mark Aronoff (2007) Language. Scholarpedia, 2(5):3175.
- Matteo Gagliolo (2007) Universal search. Scholarpedia, 2(11):2575.
Algorithmic Complexity, Algorithmic Information Theory, Algorithmic Probability, Algorithmic Randomness, Recursion Theory, Universal Search
Category:Algorithmic Information Theory Category:Computational Intelligence Category:Computer Science