Kolmogorov complexity function

The (plain) complexity C(x) of a binary string x is the length of a shortest program p such that U(p)=x, i.e. the (plain) universal Turing machineMathworldPlanetmathPlanetmath on input p, outputs x and halts. The lexicographically least such p is denoted x. The prefix complexity K(x) is defined similarly in terms of the prefix universalPlanetmathPlanetmathPlanetmath machine. When clear from context, x is also used to denote the lexicographically least prefix program for x.

Plain and prefix conditionalMathworldPlanetmathPlanetmath complexities C(x|y),K(x|y) are defined similarly but with U(x|y)=x, i.e. the universal machine starts out with y written on its worktape.

Subscripting these functions with a Turing machineMathworldPlanetmath M, as in KM(x|y), denotes the corresponding complexity in which we use machine M in place of the universal machine U.

Title Kolmogorov complexity function
Canonical name KolmogorovComplexityFunction
Date of creation 2013-03-22 13:43:49
Last modified on 2013-03-22 13:43:49
Owner tromp (1913)
Last modified by tromp (1913)
Numerical id 9
Author tromp (1913)
Entry type Definition
Classification msc 68Q30
Synonym algorithmic entropy
Synonym information content