Algorithmic Information Theory

Got it! This site "www.creationpie.org" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.

The foundations of AIT (Algorithmic Information Theory) are from Chaitin and Kolmogorov and have to do with the relationship between information and randomness. The increased complexity of the information at each level appears to include a degree of randomness.

AIT makes this connection much more precise.

Computer science is the search for finite representations of (potentially) infinite objects.

The more finite the time, the less time it takes.
The more finite the space, the less space it takes.

Taken to the extreme: AIG - Algorithmic Information Theory (Chaitin, Kolmogorov, etc.).

Information theorist Gregory Chaitin (determining randomness) showed that there is no algorithm for determining whether a sequence of symbols is random. One must be informed of this. That is, one must go outside the system.

This forms the basis of AIT as in the smallest program that can output a given output.

Most of Chaitin's ideas on AIT were already known and published by Andrey Kolmogorov (Soviet mathematician) (Андре́й Колмого́ров) whose groundbreaking work in information theory was in Russian and, at the time, not widely published outside the U.S.S.R.

Even work that was published outside of the U.S.S.R. underwent censorship which obscured some of the meaning of the work.

The book "Meta math!" by Gregory Chaitin has a good historical background of computability as will as his own basis for algorithmic information theory - the connection of randomness and information and computability and non-computability.

Chaitin uses LISP, a simple programming language based on the lambda calculus, for experimenting with and defining the size of information algorithmically.