420 views
0 votes
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

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
2 votes
2 votes
1 answer
2
hs_yadav asked Oct 6, 2017
632 views
L(M)=RL(Recursive Language) ...M is a TM...Question/Doubt:-L(m) is decidable or not (Explain by the concept of Rice Theorem)???
2 votes
2 votes
0 answers
4