View source for Algorithmic information theory

==Overview==
<span id="secInt"></span> 

'''Algorithmic information theory (AIT)''' is the
[[information theory]] of individual objects, using
[[computer science]], and concerns itself with the
relationship between computation, information, and randomness.

The information content or complexity of an object can be measured by
the length of its shortest description. For instance the string
 "0101010101010101010101010101010101010101010101010101010101010101"
has the short description "32 repetitions of '01'", while
 "1100100001100001110111101110110011111010010000100101011110010110"
presumably has no simple description other than writing down the string
itself. More formally, the [[Algorithmic Complexity| Algorithmic "Kolmogorov" Complexity]]
(AC) of a string <math>x</math> is defined as the length of the shortest
program that computes or outputs <math>x\ ,</math> where the program is run on
some fixed reference universal computer.

A closely related notion is the probability that a universal
computer outputs some string <math>x</math> when fed with a program chosen
at random. This [[Algorithmic Probability|Algorithmic
"Solomonoff" Probability]] (AP) is key in addressing the old
philosophical problem of [[induction]] in a formal way.

The major drawback of AC and AP are their incomputability.
Time-bounded "Levin" complexity penalizes a slow program by adding
the logarithm of its running time to its length. This leads to
computable variants of AC and AP, and [[Universal Search|Universal "Levin" Search]]
(US) that solves all inversion problems in optimal (apart from some unrealistically large
multiplicative constant) time.

AC and AP also allow a formal and rigorous definition of randomness
of individual strings that does not depend on physical or
philosophical intuitions about nondeterminism or likelihood.
Roughly, a string is [[Algorithmic Randomness|Algorithmic "Martin-Loef" Random]] (AR) if it is incompressible in the sense that its algorithmic complexity is equal to its length.

AC, AP,  and AR are the core subdisciplines of AIT, but AIT spawns
into many other areas. It serves as the foundation of the
[[Minimum Description Length]] (MDL)
principle, can simplify proofs in computational complexity theory,
has been used to define a universal similarity metric between
objects, solves the Maxwell daemon problem, and many others.