Kolmogorov complexity ($C_U(\sigma )$)

Kolmogorov complexity measures the length of a shortest effective description of an object. Fixing an optimal description machine gives an invariant quantity up to an additive machine-dependent constant. Plain Kolmogorov complexity is especially convenient for counting descriptions shorter than a binary string.

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.

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.

If an infinite computably enumerable family contained only incompressible strings, select its first enumerated string of length at least $n$. This is a total computable selection rule, and its selected string has a description of length $O(\log n)$ encoding the threshold. For large $n$ that is shorter than the selected string. This contradiction proves immunity.

A description machine is a partial computable map from finite binary programs to finite binary outputs. It is optimal if, for every other description machine $V$, there is a constant $c_V$ such that $C_U(\sigma )\le C_V(\sigma )+c_V$. Encoding an interpreter index in a fixed prefix gives the constant-overhead descriptions used in incompressibility arguments.