Kolmogorov complexity

In computer science, Kolmogorov complexity, (also known as descriptive complexity, Kolmogorov-Chaitin complexity, or algorithmic entropy) of an object such as a piece of text is a measure of how much information is needed to specify the object. More formally, complexity of a string is the length of the string's shortest description in some description language. It can be shown that that the Kolmogorov complexity of any string cannot be too much larger than the length of the string itself. Strings whose Kolmogorov complexity is small relative to the string's size are considered to be not complex. For example consider the following two bistrings of length 100

Related Topics:
Computer science - String

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

1100100001100001110111101110110011111010010000100101011110010110001101111111010001100011011001110111

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The first string admits a simple English language description namely "50 repetitions of "01"". The second one has no obvious simple description other than writing down the string itself.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The notion of Kolmogorov complexity is surprisingly deep and can be used to state and prove impossibility results akin to Gödel's incompleteness theorem and Turing's halting problem.

Related Topics:
Gödel's incompleteness theorem - Turing's halting problem

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Algorithmic information theory is the area of computer science that studies Kolmogorov complexity and other complexity measures on strings (or other data structures). 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).

Related Topics:
Data structure - Andrey Kolmogorov - Ray Solomonoff - Gregory Chaitin - 1960s - Leonid Levin

~ ~ ~ ~ ~ ~ ~ ~ ~ ~