Can these two languages be reduced to one another?

Question

Given:

$L_1=\left\{ \left\langle M\right\rangle :L\left(M\right)\ni w_{0}\right\}$

$L_2=\left\{ \left\langle M\right\rangle :L\left(M\right)=\left\{ w_{0}\right\} \right\}$

I believe I've managed to show that:

• $L_1 \in \mathcal{RE \setminus R} $ since it's easy to construct the acceptor:

U(<M>):
  if <M> is an invalid encoding of a TM:
    REJECT
  emulate M(w_0)
  if M accepts:
    ACCEPT
  if M rejects:
    REJECT

But according to Rice's Theorem $L_1\notin \mathcal{R}$.

• $L_2 \notin \mathcal{RE}$ since $\overline{H_{TM}}\leq_{m} L_2 $ where $\overline{H_{TM}}$ is the complement of the halting problem, which we know to be unrecognizable. I defined $f( \left\langle M,w\right\rangle) = \left\langle M^{\prime}\right\rangle$ s.t.:

M'(x):
  if x==w_0:
      ACCEPT
  if <M> is an invalid encoding of a TM:
    if x==w_0:
      ACCEPT
    else
      REJECT
  emulate M(w)
  if M halts:
    REJECT

These two proof attempts are not related, but they are two parts of the same question - So first I tried showing that $L_2 \leq_{m} L_1 $ which seems intuitively correct but I couldn't work it out. Then I got to think about it and since it's quite difficult to come up with an acceptor for $L_2$ or $\overline{L_2}$ it seems to me more like that $L_2 \notin \mathcal{RE}$.

I'm pretty confident that my proof for $L_1 \in \mathcal{RE \setminus R} $ it correct, but as for $L_2$, I tried so many versions of the pseudocode for $M^\prime$ (including a reduction from $\overline{A_{TM}}$) and I still can't convince myself that I got it right.

What bothers me the most is that nothing assures me $ \left\langle M,w\right\rangle \in \overline{H_{TM}} \implies \left\langle M^\prime\right\rangle \in L_2 $: As far as $M^\prime$ concerned, it might also get a valid encoding of $M$ and some $w$ on which it halts, but if $x=w_0$, then $M^\prime$ will accept anyways, which contradicts the definition of the reduction. Am I getting something wrong?

Any help would be appreciated, and if you're impressed I haven't fully grassped the methodology behind reductions, references to better explainations (other than the classic textbook's examples) would be great as well.

EDIT:

Okay, I now understand how to show that some language is unrecognizable via reductions from $\overline{A_{TM}}\notin\mathcal{RE}$ and $A_{TM}\notin co\mathcal{RE}$.

So I tried it with $L_{2}$: $A_{TM}\leq_{m}L_{2}$ seems about right, it resembles Yuval's suggestion in the comments, but I have the same trouble I had earlier convincing myself that the reduction from $\overline{A_{TM}}$ makes sense.

---

$A_{TM}\leq_{m}L_{2}$

We show $f\left(\left\langle M,w\right\rangle \right)=\left\langle M^{\prime}\right\rangle$ s.t. $M^{\prime}\left(x\right)$:

M'(x):
  if x==w_0:
      emulate M(w)
  else:
    LOOP

1. $\left\langle M,w\right\rangle \in A_{TM}\implies L\left(M^{\prime}\right)=\left\{ w_0\right\} \implies\left\langle M^{\prime}\right\rangle \in L_{2}$

2. $\left\langle M,w\right\rangle \notin A_{TM}\implies L\left(M^{\prime}\right)=\emptyset\implies\left\langle M^{\prime}\right\rangle \notin L_{2}$

Therefore, $A_{TM}\leq_{m}L_{2}$, and since $A_{TM}\notin co\mathcal{RE} \implies L_{2}\notin co\mathcal{RE}$

In this case, both implications are intuitive and make sense.

---

$\overline{A_{TM}}\leq_{m}L_{2}$

We show $f\left(\left\langle M,w\right\rangle \right)=\left\langle M^{\prime}\right\rangle$ s.t. $M^{\prime}\left(x\right)$:

M'(x):
  if x!=w_0:
      emulate M(w) 
      if M accepts:
        ACCEPT
  else:
    ACCEPT

Thus:

1. $\left\langle M,w\right\rangle \in\overline{A_{TM}}\implies L\left(M^{\prime}\right)=\left\{ w_0\right\} \implies\left\langle M^{\prime}\right\rangle \in L_{2}$
2. $\left\langle M,w\right\rangle \notin\overline{A_{TM}}\implies L\left(M^{\prime}\right)=\overline{\left\{ w_0\right\} }\implies\left\langle M^{\prime}\right\rangle \notin L_{2}$

Therefore, $\overline{A_{TM}}\leq_{m}L_{2}$, and since $\overline{A_{TM}}\notin\mathcal{RE} \implies L_{2}\notin\mathcal{RE}$

In this case, the 2nd implication is really intuitive but the 1st one doesn't seem right.

Answer 1

It is easy to reduce $L_1$ to $L_2$: given a Turing machine $M$ and an input $w_0$, construct another Turing machine $M'$ that runs $M$ if the input is $w_0$, and loops on any other input. Then $w_0 \in L(M)$ iff $L(M') = \{w_0\}$.

In contrast, you cannot reduce $L_2$ to $L_1$, since otherwise the halting problem would be co-r.e. Stated differently, if there is a computable reduction from $L_2$ to $L_1$, then the non-halting problem (on empty input, say) is recursively enumerable. Given a machine $M$, construct a machine $M'$ which halts if the input is $0$, and otherwise clears the tape and runs $M$. Then $M$ doesn't halt on the empty input iff $L(M') = \{0\}$. If you could computably reduce $L_2$ to $L_1$, then this would give an r.e. algorithm for deciding whether $M$ doesn't halt on the empty input.

---

The halting problem reduces to both $L_2$ and $\overline{L_2}$. Given a Turing machine $M$ and an input $x$:

1. Construct a Turing machine $M'$ which on input $x$ executes $M$, and otherwise loops. Then $M$ halts on $x$ iff $L(M') = \{x\}$.
2. Construct a Turing machine $M''$ which on input $x$ executes $M$, on input $1x$ halts, and otherwise loops. Then $M$ halts on $x$ iff $L(M'') \neq \{1x\}$.

This shows that $L_2$ is neither r.e. nor co-r.e.