0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Hi 👋, what does $M'$ in $\langle M' \rangle$ denote? $\endgroup$
    – Knogger
    Commented Feb 24 at 22:33
  • $\begingroup$ Ah, sorry. I meant ⟨M′⟩ to denote the output of f() which would be a TM description. $\endgroup$
    – Diode
    Commented Feb 24 at 22:44
  • $\begingroup$ 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. $\endgroup$
    – Knogger
    Commented Feb 24 at 23:15
  • $\begingroup$ Thanks. Edited. $\endgroup$
    – Diode
    Commented Feb 25 at 1:42

1 Answer 1

0
$\begingroup$

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}$.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Diode
    Commented Feb 24 at 22:45
  • $\begingroup$ No problem 😀 Don't worry if you're having a hard time finding reductions, it's mostly a matter of experience. $\endgroup$
    – Knogger
    Commented Feb 24 at 23:22
  • $\begingroup$ 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)? $\endgroup$
    – Diode
    Commented Feb 25 at 22:25
  • $\begingroup$ 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? $\endgroup$
    – Diode
    Commented Feb 25 at 22:39
  • $\begingroup$ 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. $\endgroup$
    – Knogger
    Commented Feb 26 at 14:56

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.