Kolmogorov Complexity

Algorithmic complexity, algorithmic entropy

Also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. Kolmogorov complexity is the length of the shortest computer program that can output a given solution. It is also defined as the computational resources needed to describe an object.

This measure of complexity is based on the length of the shortest program needed to describe any given string. It serves as one of the key indicators for measuring the complexity of finite-length data sequences. It defines the minimum length of a program that can reproduce the given data such as

MDL does.

Interpretation

Kolmogorov Complexity is similar to a natural loss function for emergence, where lower complexity implementations appear first. As a result, other programs that emerge temporally later are not selected in

Evolution due to their delayed appearance.

Kolmogorov complexity

In algorithmic information theory, the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. It is named after Andrey Kolmogorov, who first published on the subject in 1963 and is a generalization of classical information theory.