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

cs.stackexchange https://cs.stackexchange.com/questions/105089

質問

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?

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top