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!