Algorithmic information theory

Algorithmic information theory studies information and randomness through the lengths of shortest programs that produce objects. Its central measure, Kolmogorov complexity, depends on a chosen universal description language only up to an additive constant.

Kolmogorov complexity: The length of the shortest program that produces a given object on a fixed universal machine. It is the central measure of description length in algorithmic information theory.
Invariance theorem: The theorem that universal description languages yield Kolmogorov complexities differing by at most a constant. It explains why complexity is meaningful despite depending on a reference machine.
Minimum description length: A statistical principle that selects models minimizing the combined description lengths of model and data given the model. It turns algorithmic description length into a practical rule for balancing fit and model simplicity.
Andrey Kolmogorov: A Soviet mathematician who made foundational contributions to probability theory and introduced a definition of descriptive complexity. His independent formulation gave the field its most widely used complexity measure.
Uncomputability of Kolmogorov complexity: The result that no algorithm computes exact Kolmogorov complexity for every finite string. It is the central obstacle to applying the theory's ideal measure directly.
Universal Turing machine: A Turing machine that can simulate any other Turing machine given an encoded description. Its choice defines program lengths, while invariance limits differences between choices.
Algorithmic probability: A probability distribution that assigns weight to outputs in proportion to the programs that produce them. Summing program weights turns description length into a predictive probability.
Inductive inference: The process of inferring general patterns or rules from observed examples. Universal algorithmic probability formalizes prediction by favoring outputs with shorter generating programs.
Ray Solomonoff: An American mathematician and computer scientist who developed algorithmic probability and a theory of inductive inference. His universal prior connects program enumeration with prediction.
Chaitin's constant: A real number giving the halting probability of a universal prefix-free machine. Its bits encode halting information that no effective procedure can fully determine.

Linked from 6 pages