The Gateway to Computer Science Excellence
+2 votes
L1 = {<M> | M is a TM and L(M) ⊆ {00, 11}}

R.E or not RE..??
in Theory of Computation by Boss (12.2k points) | 391 views

2 Answers

+6 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
by Veteran (57.2k points)
edited by
if ϕ was not present then it would be RE right ?

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

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 :)
+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.
by Boss (12k points)
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 :)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,253 answers
104,700 users