Algorithmic information theory

From Wikipedia, the free encyclopedia

This article or section is in need of attention from an expert on the subject.
WikiProject Computer science or the Computer science Portal may be able to help recruit one.
If a more appropriate WikiProject or portal exists, please adjust this template accordingly.

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." ^[1]

Algorithmic information theory principally studies Kolmogorov complexity and other complexity measures on strings (or other data structures). Because 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 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, in any theory you can only compute finitely many digits of Ω, so it is in some sense unknowable, providing an absolute limit on knowledge that is reminiscent of Gödel's Incompleteness Theorem. Although the digits of Ω cannot be found, many general properties of Ω are known; for example, it is known to be normal and transcendental.