HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$ halts on input $w$

The complement of HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$ doesn't halt on input $w$

Show that HALT$_{TM}$ is turing reducible to its complement, and explain why it's impossible for it to me many-one reducible.

Regarding the Turing reduction, I've made reduction proofs using using A$_{TM}$ and HALT$_{TM}$ but this doesn't make sense to me intuitively.

I understand the concept of many-one reduction using the Oracle, but have difficulty applying it, not being given any examples to work with.

I'd hugely appreciate it if someone could help me approach the above question, I'm more concerned with the approach rather than the answer, as I've an exam tomorrow!

Thanks a lot.


1 Answer 1


Suppose $HALT$ was many one reducible to $\overline{HALT}$. Let the mapping function be $f$. We construct a machine $D$. It takes input $\langle M,w \rangle$ obtains the string $f(\langle M,w \rangle)=\langle M^{'},w^{'} \rangle$. $D$ simulates $ M$ on $w$ and $M^{'}$ on $w^{'}$. If the first simulation ends $D$ accepts if second simulation ends/halts it rejects. $D$ is a decider for $HALT$ which is not possible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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