The Halting Problem Relativized to Complements
Louise Hay · Proceedings of the American Mathematical Society · 1973
Let ${H^A} = \{ e|{\text {domain}}\{ e\} \cap A e \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$.