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)

  • $\begingroup$ 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. $\endgroup$ – Michael Blondin Nov 30 '14 at 2:24
  • $\begingroup$ @Michael Blondin:Yes that's it. $\endgroup$ – user2736738 Nov 30 '14 at 2:28
  • 1
    $\begingroup$ Why are you "clueless at "exactly 2 strings""? What is your intuition, do you think it decidable or not? $\endgroup$ – Michael Blondin Nov 30 '14 at 2:31
  • $\begingroup$ @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? $\endgroup$ – user2736738 Nov 30 '14 at 2:46
  • $\begingroup$ Sounds like Rice's theorem. $\endgroup$ – Ran G. Nov 30 '14 at 2:57

This is a trivial application of Rice's theorem.


$$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$.

  • $\begingroup$ G:RE-recursively enumerable. How can you say that it is a subset RE. $\endgroup$ – user2736738 Nov 30 '14 at 5:27
  • $\begingroup$ $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$. $\endgroup$ – Ran G. Apr 4 '15 at 21:45
  • $\begingroup$ Good start. Now is $A$ co-RE? $\endgroup$ – Rick Decker Jun 4 '15 at 1:38
  • $\begingroup$ @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 $\endgroup$ – Ran G. Jun 4 '15 at 3:35

Your Answer

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

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