Kolmogorov complexity function
The (plain) complexity of a binary string is the length of a shortest
program such that , i.e. the (plain) universal Turing machine on
input , outputs and halts. The lexicographically least such is
denoted .
The prefix complexity is defined similarly in terms of the prefix universal
machine. When clear from context, is also used to denote the
lexicographically least prefix program for .
Plain and prefix conditional complexities are defined similarly
but with , i.e. the universal machine starts out with written
on its worktape.
Subscripting these functions with a Turing machine , as in
, denotes the corresponding complexity in which we use machine
in place of the universal machine .
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 |