Reducing from the complement of the Halting Problem

Question

Consider the halting problem $HALT_{TM} = \{\langle M, w\rangle: M \text{ is a TM that halts on input } w\}$,

and some undecidable Language $L$ of the form $L = \{\langle M\rangle: M \text{ does a thing} \}$.

If I want to reduce the halting problem to $L$, from what I understand, I have to construct a Turing Machine $M'$ which takes the input $\langle M, w\rangle$, and if $M$ halts on $w$, $M'$ does the thing, otherwise, $M'$ does not do the thing.

Now, I want to reduce the complement of the halting problem to $L$. Meaning, I need to construct a Turing Machine $M''$ with the following:

• If $M$ halts on $w$, then $M''$ does not do the thing.
• If $M$ does not halt on $w$, then $M''$ does the thing.

The first part seems simple to implement, if $M$ halts on $w$, then $M''$ can be forced to enter into an infinite loop. But then, I need $M''$ to do the thing whenever $M$ does not halt on $w$, which from my understanding is the very definition of the halting problem - since I don’t know whether $M$ will ever halt on $w$, I cannot ever do the thing. Does that mean a reduction is not possible, or is my approach/understanding wrong?

Answer 1

For the question to be understandable, you should indicate that "a machine does a thing" actually means that "a machine performs some finite computation and then halts". Anyway, this should clarify the reduction concept to you:

Note that by reducing from the complement of the halting problem, that is from $\overline{HALT_{TM}} = \{ \langle M, w\rangle: \text{$M$ is a TM that does not halt on $w$} \}$, then you (by you I mean the reduction) need, upon getting in put of the form $\langle M, w\rangle$, to construct, halt and output a description of a machine $\langle M''\rangle$ such that $\langle M'' \rangle\in L$ only when $\langle M, w \rangle \in \overline{HALT_{TM}}$. That is, $M''$ "does a thing" iff $M$ does not halt on $w$.

There is a fine line here that you need to understand. You (the reduction) does not simulate the run of $M$ on $w$ indefinitely, and in fact, you have to halt on any input of yours. Instead, you construct a machine $M''$, based on the description of $M$ and $w$. Now $M''$ need not be a decider machine, and we don't care as long as we (the reduction) always halt and output its description. So the reduction is usually not the one that simulates the run of $M$ on $w$, it just outputs a description of $M''$, and $M''$, upon reading one of its inputs, can simulate the run of $M$ on $w$, or do whatever it is defined to do.

Note: if the reduction somehow wants to simulate the run of $M$ on $w$, then it must do that for a finite number of steps as it must eventually halt. Anyway, this is usually not the case. The right way to think of the reduction is as a black box (a TM), that gets $\langle M, w\rangle$ as input, runs for a finite number of steps, and then outputs $\langle M'' \rangle$.