658 views
3 votes
3 votes
$L=\{\langle M \rangle\mid M$ is a TM such that if $M$ accepts $w$ then $M$ accepts $ww$ also$\}$
 
Which of the following is correct?
 
 
  1. $L$ is decidable
  2. $L$ is recognizable but undecidable
  3. $L$ is unrecognizable and $\bar L$ is decidable
  4. $L$ is unrecognizable and $\bar L$ is undecidable

2 Answers

Best answer
3 votes
3 votes
Taking $L$ as a property of r.e. languages, we can have $L_{yes} = \{0, 00, 0000, \dots\}$ and $L_{no} = \{0, 00, 0000, \dots\} \cup \{000\}$. Here $L_{yes} \subset L_{no}$ and hence $L$ is a non-monotonic property. Rice's second theorem is applicable and so $L$ is not r.e. (unrecognizable).

For $\bar L$ also the same thing works. Here the property is "contains the description of $M$ such that if $M$ accepts $w$ and $M$ does not accept $ww$. We can have $L_{yes} = \{0\}$ and $L_{no} = \{0, 00, 000, \dots\} $. Here $L_{yes} \subset L_{no}$ making $\bar L$ a non-monotonic property.

So, both $L$ and $\bar L$ are not r.e. (unrecognizable). The matching option here is option D.
selected by
0 votes
0 votes
it's undecidable becz if this tm can answer if it accepts w than it accepts ww ,than halting problem will be solved