search
Log In
3 votes
477 views
L1 = {<M> | M is a TM and L(M) ⊆ {00, 11}}

R.E or not RE..??
in Theory of Computation 477 views

2 Answers

8 votes
 
Best answer
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

edited by
0
if ϕ was not present then it would be RE right ?
0

no..then other conditions are there..see extended rice..

0
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.
0
"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
0
i was wrong... it would be not RE... satisfied :)
2 votes
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.
0
alright..thankyou..can it also be proved by rice theorem??
0
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  :) ???
0
yes Rice's theorem can be applied straight away.
0
k :)

Related questions

6 votes
2 answers
1
1.8k views
My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$ I have to check that it is Turing Recognizable or not (i.e R.E) My Approach/Doubt Question taken from https://gateoverflow.in/7427/which-following ... $100$ $T_{yes}\subset T_{no}$. Hence it is not RE.But in the solution it is R.E.
asked Sep 9, 2017 in Theory of Computation sourav. 1.8k views
3 votes
1 answer
2
325 views
L={⟨M⟩|TM accepts exactly 154 strings} -------------------------------------------------------------------------------------------------------- this language is not decidable but is this R.E?? by second rice theorem, Tyes ={154 strings} and Tno = more than 154 strings hence, Tyes is subset of Tno.so,it is not even R.E. am i right? please correct me.
asked Dec 16, 2016 in Theory of Computation Akriti sood 325 views
8 votes
2 answers
3
2.2k views
$L=\left \{ <TM> | TM\ halts\ on\ every\ input\ \right \}$ is above language Recursively enumerable or non recursively enumerable??
asked Dec 16, 2016 in Theory of Computation Akriti sood 2.2k views
...