-1
$\begingroup$

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.??

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ oops. i edited my question. Sorry. $\endgroup$ – a d May 13 '13 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.