# 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 KolmogorovComplexityFunction 2013-03-22 13:43:49 2013-03-22 13:43:49 tromp (1913) tromp (1913) 9 tromp (1913) Definition msc 68Q30 algorithmic entropy information content