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.??
$\begingroup$
$\endgroup$
0
Add a comment
|
$\begingroup$
$\endgroup$
1
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.
