# Mapping Reduction from HALT?

I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would finish my proof that L isn't even recognizable. Now I'm stuck. I just can't seem to master creating mapping reductions.

I know I need to develop f() where: if (〈M〉,w) is in HALT, then f(〈M〉,w) = 〈M'〉 is in co-L and if (〈M〉,w) is not in HALT, then 〈M'〉 is not in co-L but I've wasted a day and a half on this on reduction.

I'd really appreciate some guidance on a general strategy for developing the function, f(). I keep getting caught up in w versus c and the input (which I called x) to M'.

Thank you for any direction.

• Hi 👋, what does $M'$ in $\langle M' \rangle$ denote? Commented Feb 24 at 22:33
• Ah, sorry. I meant ⟨M′⟩ to denote the output of f() which would be a TM description. Commented Feb 24 at 22:44
• So you meant "... $f(\langle M, w \rangle) = \langle M' \rangle$ is in co-L ..." instead of "... $f(\langle M' \rangle)$ is in co-L..."? You can use the "edit" button right below your question to fix that section if that's the case. Commented Feb 24 at 23:15
• Thanks. Edited. Commented Feb 25 at 1:42

Define the reduction $$f$$ such that $$f(\langle M, w \rangle) = \langle M' \rangle$$, where $$M'$$ is a TM that on word $$x$$

1. simulates $$M$$ on $$w$$ if $$x = c$$
2. halts

It's easy to see that

$$M \text{ halts on } w \iff M' \text{ halts on } c$$

therefore

$$\langle M, w\rangle \in \texttt{HALT} \iff f(\langle M, w \rangle) = \langle M'\rangle \in \overline{L}.$$

So $$\texttt{HALT} \preceq_{M} \overline{L}$$.

• Thank you so much for that answer. I tried that days ago. Why is this so hard to get? The definitions are straight-forward. Thanks again. Commented Feb 24 at 22:45
• No problem 😀 Don't worry if you're having a hard time finding reductions, it's mostly a matter of experience. Commented Feb 24 at 23:22
• Looking at this again today, shouldn't step 2 be loop? Otherwise, I'm not sure how you get M' halts on c ==> M halts on w (it seems that M' can halt on two different sets of conditions)? Commented Feb 25 at 22:25
• And, if I may, where doe the input x to M' come from? I'm so confused. Or is M' assumed to run over the domain of co-L? Commented Feb 25 at 22:39
• If step 2. was loop, then $L(M') = \emptyset$ since $M'$ would loop on any input. When you run $M'$ on $c$, then $M'$ simulates $M(w)$. So if $M(w)$ loops, then $M'(c)$ must loop as well. If $M(w)$ terminates, then $M'(c)$ must terminate as well due to step 2. Commented Feb 26 at 14:56