Self doubt

Question

REF: https://gateoverflow.in/76419/decidability

Consider the language:

1) L = {<M>| L(M) = $\epsilon$ } 

2) L = {<M>| M accepts epsilon }

Now, lets consider the 1st language: It will contain all TM encodings for TM's that accept $\epsilon$.

Now, this is totally undecidable as per Rice's theorem. Should it be interpreted in this way?

Now, this T.M ( highlighted in Red) cant tell anything and hence, its totally undecidable, right?

------------------------------------------------------------------------------

Now, the second language contains all turing machine encodings that atleast accept $\epsilon$ 

Now, if the 1st language is totally undecidable, how come 2nd is RE(but not recursive)  since, the 1st language is base for this?

Also, other question is if we can have finite automata that accepts $\epsilon$, then we can also have TM that accepts $\epsilon$, right?

Answer 1

In the first language u should also see that turing machine is not accepting any string other than epsilon
when i give u encoding of a TM₁ and asked you "is L(TM₁)= epsilon" , u shud also check other strings are getting rejected or not
thus u wont be able to say if  L(TM₁) = epsilon, as  this turing machine might loop infinitely on some string and u wont be able to say that it rejects every other string. so the language not even RE

but 2nd one is different. u just need to check for epsilon. which is RE

Comments

i have one doubt..@sushant ,@mohit,@anusha...you siad above that "

 I am pretty much sure that we can have TM that accepts only ϵ"

are u saying that above lnaguage is R.E??

how can it be R.E

/how will we make sure that it is not accepting any other string..how can u check the only part??

---

@akriti first language is not even RE and 2nd language is RE

---

@akriti, when we said we can make a TM which accept only epsilon we are saying that we can amke a TM which only accept epsilon and here we are talking of a perticular TM like you can make a perticualr F.A which accept nly epsilon, so just like that we can make a TM such that it is in its starting state and w/o seeing anything it to final state, and as it goes to final state, it will remain in same state for entire lifetime but when we are saying

L = {<M>| L(M) = ϵ }  here we are taking case of UTM which is basically taking  i/p as other TM encoding  in which case we can't decide even for yes, because of that only case thus making lang. NON  R.E :)

Answer 2

The intuitive explanation given by @ Anusha Motamarri is fine.

I am just adding here few more lines using Rice Theorem:

$$\begin{align*} &L_1 = \left \{ <M> | \; L(M) = \epsilon \right \} \\ \end{align*}$$

• RE language property = Langugae ontaining only $NULL$
• $M_1$ is a $TM$ such that $L(M_1) = \left \{ \epsilon \right \}$. Here $M_1$ satisfies the given property.
• $L(M_2) = \left \{ \epsilon \;\; , \;\; a^{*}.b^{*} \right \}$ , here does not satisfy the given property.
• But $L(M_2) \supset L(M_1)$
• $\Rightarrow$ $L_1$ is NOT RE

$$\begin{align*} &L_2 = \left \{ <M> | \; L(M) \text{ accepts null } \right \} \\ \end{align*}$$

• Here RE language property = Langugae that accepts $NULL$
• $M_1$ is a $TM$ such that $L(M_1) = \left \{ \epsilon ,aab,ab^*\right \}$. Here $M_1$ satisfies the given property.
• All supersets of $L(M_1)$ also satisfies the above property.
• $L_2$ is Recursively enumerable.

Comments

@Debashish. When you are considering Rice theorem, you should consider the property set S that contains the languages of given property.

So, if L(M) = All regular languages

then

S= {$\epsilon$, a, b, ........(a+b)*}

and you have TM encoding for each of the elements of S.

 

Now, when you say L(M)=$\phi$ or L(M) accepts $\phi$, it should be like this:

S = {$\phi$}

So, you cant add anything more to it in second case( i.e L(M) accepts $\phi$).

 

But, had it been L(M) accepts $\epsilon$, then:

S = {$\epsilon$, a*, b*, .......}

whereas, L(M) = $\epsilon$ will have

S = {$\epsilon$}

---

red : wrong.

green : correct :

---

@Debashish. COuld you plz tell whats wrong with my understanding?