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

The Gateway to Computer Science Excellence

+3 votes

Best answer

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

+1

@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_{1} becomes not recursively enumerable.

Is this correct?

0

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

+2

@Somoshree Yes, that is correct (y)

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

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

0

There exists

x∈Σ* such that for everyy∈L(M),xy∉L(M)

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

And Q(x,y) denote that *x**y*∉*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..

+1

@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}.

0

@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.

0

L1={⟨M⟩∣ there existsx∈Σ∗ such that forevery,y∈L(M)xy∉L(M)}.

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

0

yes,

After ur last line of proof

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

So, non-monotonic property satisfies

So, nonRE

ok now?

After ur last line of proof

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

So, non-monotonic property satisfies

So, nonRE

ok now?

0

0

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

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

+1

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

0

+1

0

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

0

@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

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

0

@Mk Utkarsh how are you getting $\Sigma$^{* }for Tyes??Can you please elaborate on this point a bit more?

0

@Mk Utkarsh the property is holding if T_{yes} is $\Sigma$^{*} and the property isnt holding if T_{no} is $\phi$ and T_{yes} has to be a proper subset of T_{no} for the property to be non monotonic._{ }But $\Sigma$^{*} isnt a preoper subset of $\phi$, then how is rice's theorem applicable here?? I am not getting this :(

0

how are you saying L(M) is recursive ? there isnt any clue about L(M) in question. am i missing something ? @utkarsh

0

@Mk Utkarsh

Can this be an approach to this question?

$\Sigma$={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 doesnt belong to L_{yes}) and L_{no} =$\Sigma$^{*} (since there exists an x i.e. $\epsilon$ 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_{1} becomes not recursively enumerable.

Is this correct?

0

L

_{no}=Σ^{*}(since there exists an x i.e. ϵ such that xy belongs to L_{no}for all y belonging to L_{no}).

i lost you here, can you explain this sentence more?

0

If the language accepted by the turing machine T_{no} is $\Sigma$^{*}, then there exists such an x such that for every y belonging to L_{no}(i.e. $\Sigma$^{* }here), xy belongs to L_{no}. This is true because if we take x to be equal to $\epsilon$, then x.y= $\epsilon$.y=y which is already known to belong to L_{no}.

0

if x is $\epsilon$ then for $\forall y (xy \in L(M)$

if you don't worry about what x is as x can be anything, $xy$ will still be in $\Sigma^*$

if you don't worry about what x is as x can be anything, $xy$ will still be in $\Sigma^*$

0

Arjun sir please tell how examples are wrong?

i assumed both x and L(M) to be non empty

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

so L(M) is containing some property which is unknown but the only thing we know it prepending some string x $ \in \Sigma^*$ will violate the property of L(M). But we also know that L(M) is a language of some turing machine, this makes L(M) recursive so $\exists TM$ which satisfied L(M).

$L(T_{yes}) = L(M)$

$L(T_{no}) = \Sigma^* $

0

x cannot be $\epsilon$

if it is then $y \in L(M)$ and y $\notin L(M)$ both will be true

which is contradiction

if it is then $y \in L(M)$ and y $\notin L(M)$ both will be true

which is contradiction

+1

@Mk Utkarsh

very simple example Somoshree gave

Say L(M) ={a}

and x=a too

Say y=b

So, xy=ab which is not in L(M)

So, $T_{yes}=a$

$T_{no}=ab$

and also $T_{yes}\subset T_{no}$

So, non monotonic property is satisfied

Hence it is non RE

Hope u got it

very simple example Somoshree gave

Say L(M) ={a}

and x=a too

Say y=b

So, xy=ab which is not in L(M)

So, $T_{yes}=a$

$T_{no}=ab$

and also $T_{yes}\subset T_{no}$

So, non monotonic property is satisfied

Hence it is non RE

Hope u got it

+1

srestha i agreed to all comments and answer on this question, but i wanted to know the mistake i made so that i'll not make it in future :)

0

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,405 answers

198,629 comments

105,468 users