Kolmogorov Complexity

From The Transhumanist Wiki

From the SL4 Lexicon:

Kolmogorov Complexity:

A term from information theory. The Kolmogorov complexity of a string of bits is the length of the smallest Turing machine program that produces the bit string as output. (It is therefore somewhat dependent on one's choice of Turing machine, but since every Turing machine can be emulated by a universal Turing machine with a constant increase in program length this doesn't matter much). See http://www.idsia.ch/~marcus/kolmo.htm. See also AIXI, Algorithmic Complexity, Solomonoff Induction.