Decidability

Question

$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?

Comments

i think it is RE,

even though xy ∉ L(M), it may belong to some other L(M1), where M1 is another turing machine. and also x ∈ ∑*

---

answer is given as not re.

Answer 1

$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

Comments

Concatenation is for strings in $L$. Since there is no string in $L$, concatenation cannot happen.

---

@Arjun sir,  so when we concatenate empty language with some other language then we get empty language right?  But here we are concatenating strings right?

---

@Arjun Sir plz chk it

yes, I too think the empty set or null set is the unique set having no elements

So,

  empty set always unreachable from start state, So, it's concatenation also will be unreachable from start state

https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/lectures/15/Small15.pdf

So, how Tyes here subset of Tno

$T_{yes}=\Phi$ and also $T_{no}=\Phi$

isnot in this example Tyes=Tno?

I am not getting difference between empty set and NULL set

Answer 2

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

Comments

Somoshree ok while applying 1st part of rice's theorem i shouldn't have use $\Sigma ^*$ but is it correct now?

---

@Mk Utkarsh so what is T_yes now??

---

$L(M)$