Kolmogorov Complexity
Natural & Formal Sciences Dictionary
Definition
A measure of the algorithmic information content of a finite object, defined as the length of the shortest description (program plus input) on a fixed universal description machine that produces the object.
Kolmogorov Complexity
- Natural & Formal Sciences -
Mathematics & Logic Dictionary
Definition
The length (in bits) of the shortest effective description or program that, when run on a fixed universal Turing machine, outputs a given finite string, considered up to an additive constant depending on the choice of universal machine.