Question

L1 = {<M> | M is a TM and L(M) ⊆ {00, 11}}

R.E or not RE..??

Answer 1

1. Using dovetailing: (intuitive and best)

Property : Acceptance of a finite language $\begin{align} L(M) = \phi \cup \left \{ 00 \right \}\cup \left \{ 11 \right \}\cup \left \{ 00,11 \right \} \\ \end{align}$.

For checking any $M$ belonging to the property, we have to use an UTM  and check $\langle M,w \rangle$ pairs , feeding $w$ in a dovetailing (zigzag) manner.

We have to confirm the acceptance of some strings (as shown above) and non-acceptance of all other strings.

"non-acceptance of all other strings", this requirement is hard and TM may go infinite loop.

So we can not even check $M$ for although $M$ may belong to property.

$\Rightarrow$ $L1$ is non-computable or NOT-RE.

2. Using Rice Theorem.

$$\begin{align} T_{1_{yes}} &= \phi = \left \{ \right \} \\ T_{2_{yes}} &= \left \{ 00 \right \}
\\ T_{3_{yes}} &= \left \{ 11 \right \}
\\ T_{4_{yes}}
&= \left \{ 11,00 \right \} \\ \end{align}$$

 

Whenever $\phi \in \text{Property SET}$ then corresponding property language is NOT-RE.

Or, Some supersets of any $T_{yes}$ does not satisfy the given property. Hence NOT RE

Comments

bro.. intutively speaking since if a language accepts 00 or 11 or both (not talking about empty string) then it will yes and if it accepts any other string then we can stop and say no. only condition on which we can't say no is when it doesn't accept anything but since it can say yes it becomes RE ?      thanks for the link but i am not able to understand rice theorem therefore working intutively.

---

"only condition on which we can't say no is when it doesn't accept anything but since it can say yes it becomes RE ? "..could not understand this line.

Sometimes Rice becomes very useful

---

i was wrong... it would be not RE... satisfied :)

Answer 2

not even RE.
i should print all the turing machines which accepts 00 or 11 or both and i should make sure that it doesnt accept any string other than 00 and 11. if a particular turing machine loops infinitely on a string other than 00 and 11.. we will not be able to say "yes" for the turing machines which belong to the language.

Comments

alright..thankyou..can it also be proved by rice theorem??

---

i think it can be proved by rice theorem because rice theorem can be applied only when we have   language of the turing machine ??
@Arjun sir , @Kapil  :) ???

---

yes Rice's theorem can be applied straight away.

---

k :)