Complement of halting set is not r.e.

4.6k Views Asked by At

suppose we don't know that Halting problem is not recursive.

I want to prove that complement of halting set is not r.e. then we can find halting problem is not recursive.

Can you direct prove that complement of halting set is not r.e.??

1

There are 1 best solutions below

9
On

HINT: If a set and its complement are both recursively enumerable, the set is ... ?

Added: This hint was for the original version of the question, which assumed that the halting problem was undecidable and did not ask for a direct proof.