Kolmogorov complexity function

The (plain) complexity $C(x)$ of a binary string $x$ is the length of a shortestprogram $p$ such that $U(p)=x$, i.e. the (plain) universal Turing machine oninput $p$, outputs $x$ and halts. The lexicographically least such $p$ isdenoted $x^{\ast }$.The prefix complexity $K(x)$ is defined similarly in terms of the prefix universalmachine. When clear from context, $x^{\ast }$ is also used to denote thelexicographically least prefix program for $x$.

Plain and prefix conditional complexities $C(x|y),K(x|y)$ are defined similarlybut with $U(x|y)=x$, i.e. the universal machine starts out with $y$ writtenon 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$.