# Is the set of TMs that accept exactly two strings (each) semi-(decidable)?

I have found this problem-

let A be the set of encoding of all those Turing machines that accept exactly two strings and let A' be the complement of A. Comment on whether A and A' are recursive , recursively enumerable or not recursively enumerable.

I am clueless at "exactly 2 strings". I have tried many books but I can't solve it. Please help.(Any hint is acceptable)

• A is the set of Turing machines that recognize a language of the form {u, v} where u and v are distinct words. The question is basically whether A is decidable or not. – Michael Blondin Nov 30 '14 at 2:24
• @Michael Blondin:Yes that's it. – user2736738 Nov 30 '14 at 2:28
• Why are you "clueless at "exactly 2 strings""? What is your intuition, do you think it decidable or not? – Michael Blondin Nov 30 '14 at 2:31
• @Michael Blondin:I think I have to reduce it in a way that I can show it undecidable. And I thought that after reading "RICE's theorem".Isn't it a non-trivial property of regular language? – user2736738 Nov 30 '14 at 2:46
• Sounds like Rice's theorem. – Ran G. Nov 30 '14 at 2:57

This is a trivial application of Rice's theorem.

Define:

$$S_A = \{ L \in RE \mid |L|=2\}$$

It is a non-trivial subset of $RE$ (for instance, it contains $\{0,1\}$ and it doesn't contain $\{\varepsilon\}$). Then By Rice's Theorem

$$A = \{ \langle M \rangle \mid L(M) \in S_A\}$$ is undecidable. Note that $A$ is exactly the language stated in the question.

There is also an extended version of Rice's theorem that will show that $A$ is not even $RE$.

• G:RE-recursively enumerable. How can you say that it is a subset RE. – user2736738 Nov 30 '14 at 5:27
• $RE$ is just a set of languages. $S_A$ is also a set of languages $L\in RE$ therefore it is a subset of $RE$. – Ran G. Apr 4 '15 at 21:45
• Good start. Now is $A$ co-RE? – Rick Decker Jun 4 '15 at 1:38
• @RickDecker the same method of extended Rice's theorem will show that the complement of $A$ is also not in $RE$. Maybe this extended rice form should be added to the reference question – Ran G. Jun 4 '15 at 3:35