The halting problem is $RE$ complete. With an oracle for the halting problem could you decide problems in $co RE$ with an oracle for RE?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes. In general - for a language $L$ an oracle to $L$ is equivalent to an oracle of $\overline L$.
Since the complement of the halting problem is co-RE complete (it is immediate from the fact that the halting is RE complete), then an oracle to it can solve all co-RE.
answered Dec 22, 2021 at 20:21