# Can these two languages be reduced to one another?

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.

• In the case for $L_1$, the machine you made might loop. It doesn't always halt. If $M(w_0)$ enters a loop, then your machine loops also. – frabala Jun 9 at 23:31
• @frabala I am aware of that. But that's why it's in $\mathcal{RE \setminus R}$. I only need to show an acceptor, not a decider. Right? – gbi1977 Jun 9 at 23:57

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.

• Thanks! you made things a bit more clear to me on how to construct the code. But the result $L_1 \leq_{m} L_2$ is still only useful to deduce that $L_2 \notin \mathcal{R}$, and I still can't find a way to show if $L_2 \in \mathcal{RE}\cup co\mathcal{RE}$ or not. – gbi1977 Jun 10 at 10:32
• I suggest you keep trying. – Yuval Filmus Jun 10 at 13:33
• Do you mean: $M^{\prime\prime}(w_0)$ will emulate $M(w)$, and if $M$ halts, $M^{\prime\prime}$ rejects; $M^{\prime\prime}(1w_0)$ (or any other fixed word which is not $w_0$) accepts; And in any other case, $M^{\prime\prime}$ loops; Is this how $M^{\prime\prime}$ operates? – gbi1977 Jun 10 at 16:45
• I used $1x$ for $w_0$. – Yuval Filmus Jun 10 at 17:46
• Right, that’s the idea. – Yuval Filmus Jun 11 at 4:02