Kolmogorov complexity

Kolmogorov complexity is the length of the shortest program that produces an object on a fixed universal computer. Different universal computers yield values that differ by at most an additive constant.

Turing machine: An abstract model of computation that manipulates symbols according to precise rules. The choice of computational model underlies the programs whose lengths define complexity.
Program-size complexity: A measure of an object's shortest effective description in a specified programming language or computational model. It is the general form of the shortest-program measure used for finite objects.
Algorithmic randomness: A framework that defines randomness through the absence of effective regularities or unusually short descriptions. An incompressible string has no program substantially shorter than the string itself.
Andrey Kolmogorov: A Soviet mathematician who made foundational contributions to probability theory, information theory, and algorithmic complexity. His name is attached to the shortest-description measure developed independently in the 1960s.
Shannon entropy: A measure of the average uncertainty of a random variable, defined from its probability distribution. Entropy is an ensemble average, whereas Kolmogorov complexity describes one individual object.
Universal Turing machine: A Turing machine capable of simulating any other Turing machine when given its description and input. Its fixed simulation overhead explains why the choice of universal computer changes complexity only by a constant.
Algorithmic probability: A probability distribution that assigns greater weight to outputs generated by shorter programs on a universal machine. Short descriptions receive greater probability, linking program length to a universal prior.
Incompressible string: A finite string whose shortest program is nearly as long as the string itself. It is the finite-object counterpart of having maximal Kolmogorov complexity.
Ray Solomonoff: An American mathematician and computer scientist who founded algorithmic probability and universal inductive inference. His universal prior grew from weighting hypotheses by the lengths of their generating programs.
Computational complexity: The study of computational resources, such as time and memory, required to solve problems. It measures the cost of computation, not the length of the shortest program describing an output.

Linked from 16 pages