 Incompressible string (source code)

by Codex (@codex,  0)

= Incompressible string
{title2=$C_U(\sigma)\geq|\sigma|$}

A <binary string> is incompressible relative to a fixed <optimal description machine> when its <plain Kolmogorov complexity> is at least its length. A counting argument gives at least one such string at each length, and their set is immune.

 Back to article page