1,596 views
2 votes
2 votes

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?

2 Answers

Best answer
4 votes
4 votes

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 TM1 and asked you "is L(TM1)= epsilon" , u shud also check other strings are getting rejected or not
thus u wont be able to say if  L(TM1) = 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

selected by
2 votes
2 votes

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.

Related questions

0 votes
0 votes
1 answer
2
mrinmoyh asked Dec 27, 2018
291 views
L1 $\cap$ L2 = $\phi$ This problem is decidable or undecidable in case of CSL, REL, & REnL ????
0 votes
0 votes
0 answers
3
newdreamz a1-z0 asked Dec 22, 2018
453 views
L={ <M | ‘M’ IS A TURING MACHINE AND ‘M’ COMPUTES THE PRODUCT OF TWO NUMBERS }here what can we say about ‘L’?
2 votes
2 votes
1 answer
4
kumar.dilip asked Dec 13, 2018
462 views
If L is CFL then $\bar{L}$ is Recursive. ( True/False)If L is CFL then $\bar{L}$ is RE. (True/Flase).