2
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Mar 4, 2019 at 6:49
  • $\begingroup$ Please come to this chatroom $\endgroup$
    – John L.
    Mar 4, 2019 at 7:12
  • $\begingroup$ My reputation is not enough to talk in the chatroom. Thanks again for your explanation! $\endgroup$ Mar 4, 2019 at 16:27
  • $\begingroup$ 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$. $\endgroup$
    – John L.
    Mar 4, 2019 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.