Question

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top