1,678 views

2 Answers

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

Related questions

11 votes
11 votes
2 answers
1
sourav. asked Sep 9, 2017
4,370 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 Recogniza...
8 votes
8 votes
3 answers
3
Akriti sood asked Dec 16, 2016
4,776 views
$L=\left \{ <TM | TM\ halts\ on\ every\ input\ \right \}$is above language Recursively enumerable or non recursively enumerable??