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

@Arjun Sir Is my approach correct?

Σ={a,b}

Let the language being accepted by T_yes be L_yes and language being accepted by T_no is L_no. Let us consider L_yes={a} (since there exists an x i.e x=b such that for all y belonging to L_yes, xy doesn't belong to L_yes) and L_no =Σ^* (since there exists an x i.e. ϵ such that xy belongs to L_no for all y belonging to L_no). So as L_yes is a proper subset of L_no, so this is a non-monotonic property and hence from rice's second theorem, the language L₁ becomes not recursively enumerable.

Is this correct?

 

---

@arjun sir

by writing this statement

L(T_yes)={ } - L is having no elements and so the given property holds

do you want to say that there is no turing machine which accept the condition given in the question?

 

 

---

@Somoshree Yes, that is correct (y)

@Gurdeep No, I mean one of the Turing machine which is having the given property accepts empty language.

---

@Somoshree

Can u tell me plz what is ur x,y, and how $xy\notin L(M)$?

---

There exists x∈Σ* such that for every y∈L(M),xy∉L(M)

 

Let P(y) denote that y∈L(M)

And Q(x,y) denote that xy∉L(M) where x∈Σ*

So this statement can be written like:

∃x,∀y P(y)⋀Q(x,y)

∃x,∀y P(y)⋀Q(x,y) = {P(y1)⋀Q(x1,y1) ⋀ P(y2)⋀Q(x1,y2)⋀.....⋀ P(yn)⋀Q(x1,yn) } ⋁

{P(y1)⋀Q(x2,y1) ⋀ P(y2)⋀Q(x2,y2)⋀.....⋀ P(yn)⋀Q(x2,yn) }⋁

{P(y1)⋀Q(xm,y1) ⋀ P(y2)⋀Q(xm,y2)⋀.....⋀ P(yn)⋀Q(xm,yn) }

where yi belongs to L(M) and xj belongs to Σ*.

Now if L(M)= { } is T_yes then this predicate logic should be valid.

@Arjun Sir please help me proceed..I am stuck! And if all what i wrote is wrong then please correct me..

---

@Srestha maam Consider language L_yes is defined over $\Sigma$={a,b}. Let L_yes={a}. Then there exists an x(here x=b satisfies this property) in $\Sigma$^* such that for all y in L_yes, xy(here x.y gives the string ba which isnt present in L_yes) xy doesnt belong to L_yes.

---

yes, right :)

---

@MiniPanda

why u take for all y

it maynot true for all y

this line is very important to satisfy non-monotonic property

we have an element for "yes" case as well as "no" case, the property is non-trivial.

---

@srestha

L1={⟨M⟩∣ there exists x∈Σ∗ such that for every y∈L(M),xy∉L(M)}.
 

It should be true for all y that belong to L(M)..isn't it?

---

yes,

After ur last line of proof

$\left \{ \right \}\subset \Sigma ^{*}$

So, non-monotonic property satisfies

So, nonRE

ok now?

---

@srestha

Actually I am not getting how L(T_yes) is  { }. This might be silly but still :/

---

same here..even i am not getting as to how empty set is satisfying the condition of the language..

---

nothing is subset of everything

right?

Here { } is the string which even not contain $\epsilon$

{ } here is empty set, which is in $L(M)$

but when concatenate $\left \{ \right \}.\Sigma ^{*}=\Sigma ^{*}$ which is not in $L(M)$

So, we can apply Rice theorem

And $\left \{ \right \}\subset \Sigma ^{*}$

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

Note: Here concatenation doesnot contain empty set, but subset of concatenated set contain empty set

---

@Somoshree Suppose I say every one in the class should come with their parents. Now, if there is no one in the class, the condition is satisfied rt?

---

but when concatenate {}.Σ∗=Σ∗ which is not in L(M)

{ } concatenated with anything gives { } right?? 

---

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