= Solution
An <immune set> is an infinite set containing no infinite <computably enumerable> subset. For <binary strings>, use an effective <bijection> with <natural numbers> when discussing enumeration. Fix an <optimal description machine> $U$ and define the <plain Kolmogorov complexity>
$$
C_U(\sigma)=\min\{|p|:U(p)=\sigma\}.
$$
An <incompressible string> has no description shorter than itself, that is, $C_U(\sigma)\geq|\sigma|$. The choice of machine is fixed throughout the proof.
Let $I$ be the set of <incompressible strings>. There are $2^n$ strings of length $n$, but only $1+2+\cdots+2^{n-1}=2^n-1$ programs of length less than $n$. Each halting program describes at most one string, so at least one string of each length belongs to $I$. Consequently $I$ is infinite.
Suppose an infinite <computably enumerable set> $E$ were contained in $I$. Define a <total computable function> $q(n)$ by running an enumeration of $E$ until a string of length at least $n$ appears, and outputting the first such string. This search always terminates because there are only finitely many <binary strings> of bounded length. A fixed program can reconstruct $q(n)$ from a <self-delimiting binary code> of $n$. For example, if the binary expansion of $n$ has length $\ell$, encode it using $\ell$ copies of one, a zero separator, and its $\ell$ binary digits. This gives
$$
C_U(q(n))\leq2\lceil\log_2(n+1)\rceil+c
$$
for a constant $c$ depending on the enumeration algorithm and the <optimal description machine>, not on $n$. For sufficiently large $n$ this is less than $n\leq|q(n)|$, contradicting $q(n)\in I$. Thus \b[the set of <incompressible strings> is an <immune set>]. This proves <immunity of incompressible strings>. The argument uses the ability to describe a selected long string by the short threshold specifying how it was selected.
Back to article page
