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 . This is a total computable selection rule, and its selected string has a description of length encoding the threshold. For large that is shorter than the selected string. This contradiction proves immunity.
Articles by others on the same topic
There are currently no matching articles.