The halting problem relativized to complements

Abstract:

Let ${H^A} = \{ e|{\text {domain}}\{ e\} \cap A \ne \emptyset \}$. It is shown that there exists a set $A$ of Turing degree $a$ such that ${H^A}$ is Turing-incomparable to ${H^{\bar A}}$ whenever $a$ is an r.e. degree with $a’ > 0’$, or $a \geqq 0''$ or $a \geqq 0’$ and $a$ is r.e. in 0’. This contrasts with the fact that ${H^A}$ is comparable to ${H^{\bar A}}$ for almost all $A$.