# Question about Turing and Many-One Reductions

I have seen this statement in my studies and I cannot figure out why it is true.

We know that $$P_{HALT} \leq_T \overline{P_{HALT}}$$, but $$P_{HALT} \leq_m \overline{P_{HALT}}$$ does not hold.

I know, that If the many-one-reduction was possible, then both problems were semi-decidable, which makes the Halting problem decidable. But I would prefer a more intuitive answer.

• Do you see why $P_{HALT}\le_T\overline{P_{HALT}}$? Aug 15 at 19:46
• not really, tbh Aug 15 at 20:17

## 1 Answer

If $$P_{\mathrm{HALT}} \leq_m \overline{P_{\mathrm{HALT}}}$$ then given a Turing machine $$M$$, you can come up with another Turing machine $$M'$$ such that $$M$$ halts iff $$M'$$ doesn't halt (in both cases, we run the machine on a blank tape). Let's break this into two conditions:

1. If $$M$$ halts then $$M'$$ doesn't halt.
2. If $$M$$ doesn't halt then $$M'$$ halts.

It is easy to satisfy the first condition: $$M'$$ can simulate $$M$$, and if $$M$$ halts, enter an infinite loop. However, it is not clear how to satisfy the second condition — how can you tell that $$M$$ doesn't halt? This is, intuitively, the reason that no such reduction exists.

In contrast, $$P_{\mathrm{HALT}} \leq_T \overline{P_{\mathrm{HALT}}}$$ trivially: you can solve the halting problem given an oracle for the not-halting problem. If you don't see it immediately (as you indicate in the comments), then you haven't internalized the definition of a Turing reduction.