Algorithmic information theory
Algorithmic information theory is a subfield of
information theory and
computer science that concerns itself with the relationship between
computation and
information. According to
Gregory Chaitin, it is "the result of putting Shannon's information theory and Turing's computability theory into a cocktail shaker and shaking vigorously."
Algorithmic information theory principally studies
Kolmogorov complexity and other complexity measures on strings (or other
data structures). Since most mathematical objects can be described in terms of strings, or as the limit of a sequence of strings, it can be used to study a wide variety of mathematical objects, including the
integers and
real numbers.
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 mainly due to
Leonid Levin (1974).
Unlike classical information theory, algorithmic information theory gives formal, rigorous definitions of a
random string and a
random infinite sequence that do not depend on physical or philosophical intuitions about
nondeterminism or
likelihood.
Some of the results of algorithmic information theory, such as
Chaitin's incompleteness theorem, appear to challenge common mathematical and philosophical intuitions. Most notable among these is the construction of
Chaitin's constant Ω, a real number which expresses the probability that a random computer program
will eventually halt.
Ω has numerous remarkable mathematical properties, including the fact that it is
definable but not computable. Thus, although
Ω is easily defined, more than the first few
binary digits of
Ω are literally
unknowable, providing an absolute limit on knowledge that is reminiscent of
Gödel's Incompleteness Theorem. Although the digits of
Ω are forever unknowable, many properties of
Ω are known; for example, its digits are known to be
equidistributed.
*
Kolmogorov complexity*
Algorithmically random sequence*
Algorithmic probability*
Chaitin's constant*
Chaitinâ€"Kolmogorov randomness*
Computationally indistinguishable*
Distribution ensemble*
Epistemology*
Invariance theorem*
Limits to knowledge*
Minimum description length*
Minimum message length*
Pseudorandom ensemble*
Pseudorandom generator*
Uniform ensemble* http://www.cs.auckland.ac.nz/CDMTCS/docs/ait.html
