0 votes

L1 = { <M> | M is a TM and | L (M) <=1 }

L2= { <M> | M is a TM and | L (M) >=1 }

NOW QUESTION IS WHICH ARE RECURSIVE ENUMERABLE AND WHICH ARE NOT ????

I JUST READ BASICS OF rice theorem DONT PRACTICE MUCH QUESTIONS ON THIS

I SOLVED ABOVE QUESTION BY THIS... IS IT CORRECT ?????if any mistake plzz point out

statement 1 :

means that for all turing machines T (m).. each turing ,machine has one language which have atmost 1 string ......

now by use rice theorem .......

2 properties of theorem .......

and by using 2nd property monotonic one ------->

any non monotonic property of recursively enumerable languages is not even semi decidable..........

what is non monotonic property ??? ------> means if set having property is a proper subset of any set not having the property......

and we also want REL_ yes to be a proper subset of REL_no.....

statement 1

REL_ yes means any language of one string i.e. suppose l = { a}.

no take REL-no means which dont have one string so suppose L = {a,b,aa }

see here REL_ yes is a proper subset of rel _No

so its not rel.....

for 2nd statement ......

again i can use monotonic property ...... REL_no as string length >= 0...... and REL_yes as string length >= 1 .

REL_YES is a proper subset of REL _NO . so we can say that it is also non re

0

Arjun sir ,what is REL_ NO exactly means plzz explain ?

i generally think of REL_NO as any set i can make which is not same as REL_yes