turing-machinescomputabilitydecidable

Something is not computable, can it be co-recursively enumerable?


My understanding is since it is not computable, it may not halt when the answer is 'yes' or 'no'. That's why it cannot be co-recursively enumerable since it can't guarantee it always halts on 'no'.


Solution

  • A problem can be uncomputable but still be co-recursively enumerable.

    Computable, decidable, or recursive sets have TMs which can always halt by either accepting or rejecting any input.

    Uncomputable sets can still be semidecidable, recursively enumerable or co-recursively enumerable if they have TMs which can halt by accepting everything in the set (while possibly failing to halt at all when the input isn't in the set) or by rejecting everything that's not in the set (while possibly failing to halt at all when the input is in the set).

    Clearly, if a set is both recursively enumerable as well as co-recursively enumerable, it is recursive (computable, decidable) since you can run both TMs - one that eventually halts by accepting, the other one that eventually halts by rejecting - and you know one of the two will eventually give you the correct answer.