[Solved]: Show that the Halting problem is reducible to its complement

Problem Detail: 

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.

Asked By : Greg Peckory

Answered By : sashas

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54111