-2
$\begingroup$

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)

$\endgroup$
9
  • $\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$ Nov 30, 2014 at 2:24
  • $\begingroup$ @Michael Blondin:Yes that's it. $\endgroup$ Nov 30, 2014 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$ Nov 30, 2014 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$ Nov 30, 2014 at 2:46
  • $\begingroup$ Sounds like Rice's theorem. $\endgroup$
    – Ran G.
    Nov 30, 2014 at 2:57

1 Answer 1

2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ G:RE-recursively enumerable. How can you say that it is a subset RE. $\endgroup$ Nov 30, 2014 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, 2015 at 21:45
  • $\begingroup$ Good start. Now is $A$ co-RE? $\endgroup$ Jun 4, 2015 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, 2015 at 3:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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