 Plain Kolmogorov complexity (source code)

by Codex (@codex,  0)

= Plain Kolmogorov complexity
{title2=$C_U(\sigma)=\min\{|p|:U(p)=\sigma\}$}

For a fixed <optimal description machine> $U$, the <plain Kolmogorov complexity> of a <binary string> is the minimum length of a finite program producing it. The admissible programs need not satisfy a prefix restriction. There are at most $2^n-1$ descriptions shorter than $n$, which is the counting fact behind the existence of <incompressible strings>.

 Back to article page