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