My original intention was to prove that $L = \{\langle M \rangle \mid |L(M)| = 2 \}$ is not turing recognizable but soon I realized that I could use the complement of ATM because the complement of ATM is not turing recognizable. And there's a corollary that if $A \leq_{m} B$ and $A$ is not turing recognizable then $B$ is not turing recognizable. In this case we could prove that $L$ is not turing recognizable.

However I have trouble proving that the complement of ATM $\leq_{m} L = \{\langle M \rangle \mid |L(M)| = 2 \}$, which stands for the complement of ATM is mapping reducible to $L$.

  • $\begingroup$ Are the hints in this answer helpful to you? $\endgroup$ – John L. Mar 4 '19 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.