# Prove the languages |L<M>| = 2 and |L<M>| $\not=$ 2 to be non-Turing recognizable or non-recursively enumerable

I am trying to prove the non-recursively enumerable property of two languages.

$$L_2 = \{\langle M \rangle: |L\langle M \rangle| = 2\}$$ and
$$L_{\not=2} = \{\langle M \rangle: |L\langle M \rangle| \not= 2\}$$.

My idea is to use the following two properties:

1. If A $$\leq_m$$ B and A is not Turing recognizable then B is not Turing-recognizable.

2. A $$\leq_m$$ B if and only if $$A^c \leq_m B^c$$.

For language $$L_{2}$$, If I can show that $$A_{TM}$$ is mapping reducible to $$L_{\not=2}$$, according to property 2 we could get that $$\overline{A_{TM}}$$(the complement of $$A_{TM}$$) is mapping reducible to $$L_{2}$$, and for the fact that $$\overline{A_{TM}}$$ is not Turing recognizable, we could get that $$L_{=2}$$ is not Turing recognizable.

For language $$L_{\not=2}$$, If I can show that $$\overline{A_{TM}}$$ is also mapping reducible to $$L_{\not=2}$$, and for the fact that $$\overline{A_{TM}}$$ is not Turing recognizable, we could get that $$L_{\not=2}$$ is not Turing recognizable.

However, I don't know how to prove the mapping reducible relationships between them. Or my direction could be totally wrong.

Could somebody give me the hints or possible solutions?

If I can show that $$A_{TM}$$ is mapping reducible to $$L_{=2}$$, ...
That is a nice idea. Given $$\langle M, w \rangle$$, can you construct a TM $$M_1$$ that accepts only one word, the word $$w$$ if and only if $$M$$ accepts $$w$$?
Then, can you change $$M_1$$ so that it accepts another word that is different from $$w$$?
You can also show that $$A_{TM}$$ is mapping reducible to $$L_{\not=2}$$ by creating a TM $$M_3$$ which accepts 2 words if $$M$$ does not accepts $$w$$ and 3 words otherwise.
• Thanks for your replying! However, I am little confused about the concept of mapping reduction from $A_{TM}$. If I could construct a Turing machine, let's call it M and M could accept some input, then is it trivial to say that it is mapping reducible from $A_{TM}$ for the fact that $A_{TM}$ contains all encodings of all Turing machines that accept some input? Mar 4, 2019 at 6:49
• From $\langle M,w \rangle\in A_{TM}$, you can construct a new TM $M_w$, which accepts word $w$ and no other words. That would be a reduction from $A_{TM}$ to $\{\langle M \rangle: |L\langle M \rangle| = 1\}$. Adjust that construction a bit, you can create a reduction $A_{TM}$ to $L_2$. Mar 4, 2019 at 18:17