Immunity of incompressible strings
ID: immunity-of-incompressible-strings
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.
New to topics? Read the docs here!