# 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 |