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.??
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communitysuppose 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.??
If a set $S$ and its complement $S^C$ are both recursively enumerable, then the set $S$ and its complement $S^C$ are both recursive. Let $M$ be a TM enumerating $S$ and $M^C$ be a TM enumerating $S^C$. To decide either $S$ or $S^C$, we can use $M$ and $M^C$ in an alternating fashion (i.e., during odd-numbered steps we use $M$, and during even-numbered steps we use $M^C$) to generate all possible strings, and either accept or reject depending on which set we're deciding. This process is guaranteed to halt since, between the two machines, every possible string will be enumerated after a finite number of steps.