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 machine on input $p$, outputs $x$ and halts. The lexicographically least such $p$ is denoted $x^{\ast }$. The prefix complexity $K(x)$ is defined similarly in terms of the prefix universal machine. When clear from context, $x^{\ast }$ is also used to denote the lexicographically least prefix program for $x$.

Plain and prefix conditional 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 machine $M$, as in $K_M(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