1,982 views
3 votes
3 votes
$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$

Is $L_1$ RE or not RE?

2 Answers

Best answer
4 votes
4 votes

$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$

So, here the Turing Machine for $L_1$ must decide if any input Turing Machine $M$ is having this property. Is this property non-trivial for the recursively enumerable set?

  • $L(T_{yes}) = \{\}$ - $L$ is having no elements and so the given property holds
  • $L(T_{no}) = \Sigma^*$ - since $L$ is having all the strings, any concatenated (with any one) string, $xy$ will also be in $L$ violating the given property

(We can have any other $T_{yes}$ and $T_{no},$ I just took one)

Since, we have an element for "yes" case as well as "no" case, the property is non-trivial. Any non-trivial property of recursively enumerable set is undecidable (Rice's theorem part 1).

Here, $L(T_{yes}) \subset L(T_{no}),$ which makes the property non-monotonic. And any non-monotonic property of recursively enumerable set is not-even semi-decidable (Rice's theorem part 2) which makes its language not recursively enumerable. 

Reference

selected by
0 votes
0 votes

We can have $Tyes$ for $L(M)$ and $Tno$ for $ϕ$. Hence, $L_1$ is no recursive for sure.

$L(M)$ is recursive so obviously $\exists$ TM for it, so this TM says $T_{yes}$ for L(M) and also there exists a TM which says no for $\Sigma^*$

Any non-monotonic property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is unrecognizable

For a property of recursively enumerable set to be non-monotonic, there should exist at least two recursively enumerable languages (hence two Turing machines), the property holding for one ($Tyes$ being its TM) and not holding for the other ($Tno$ being its TM) and the property holding set (language of $Tyes$) must be a proper subset of the set not having the property (language of $Tno$).

we are pretty sure that $L(M)$ is a proper subset because it is given in the definition of the $L_1$ there exists x ϵ Σ* such that for every y ϵ L(M), xy ∉ L(M).

So there exist a TM which is holding properties of L(M), which can say $Tyes$ for L(M), and another TM which says $Tno$ for $\Sigma^*$. 

$L(M) \subset \Sigma^*$

Property holding set is non monotonic because it is proper subset of of the set $ \Sigma^*$

Hence $L_1$ is non RE

edited by

Related questions