Given the following language: $$L=\left \{ <M> | \exists L \in R \quad s.t \quad L(M)\subseteq L \right \}$$ I need to determine it's compuation class(R or RE).

I used Rice Theorem as follows to say it's not in R:

The prperty is non trivial:
$L(M_{1}) \subseteq L \subseteq L(M_{2})$
from this property I can infer that L(M1) is indeed a subset of L but the same doesn't necessary apply to L(M2)
and the condition of the language L indeed describes a property:
for example:
Both are halting and accept the same strings, meaning:
$L(M_{1})\subseteq L$ and also $L(M_{2}) \subseteq L$
$L(M_{1})\nsubseteq L$ and also $L(M_{2}) \nsubseteq L$
Following this convenction L is not in R.

Now my problem starts with the class RE:
My logic tells that if $L \in R$ (the L in the condition)then I can build a tm(M*) which describe the language and it's like saying that $L(M) \subseteq L(M*)$(just replace the L with $L(M*)$)
L(M) is "bigger" group than L(M*) ($RE>R$) then I can just check this condition by running all string in L(the one in the condition) and see and if I find some input which it halts on, I will decide according the machine state("accept" or "reject") but then the language is in R which contradicts the "proof" that it is not in R using Rice Theorem.
Maybe I just didn't understand the problem (or rice theorem...).
If any direction can be given to how approach this problem and if my way of trying to solve the problem is valid would be appreciated.

  • 3
    $\begingroup$ Actually, this property is trivial. Hint: recall that $\Sigma^*\in R$. $\endgroup$
    – Shaull
    Aug 28 at 18:12
  • $\begingroup$ You use $L$ twice, with different meanings. $\endgroup$
    – vonbrand
    Aug 30 at 1:19

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.