# SELF DOUBT _ RICE THEOREM

123 views

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

1
It is correct till the last part. Your REL_NO is wrong for L2.
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

0
okk we cant accept  epsilon by turing machine.....so not >=0

## Related questions

1
426 views
Problem : It is undecidable whether an arbitrary Turing Machines halt within 10 steps? Let consider Two Turing machine in which first one it is halt in 10 steps while in other it is not , so as it is undecidable. @arjun sir ,@bikram sir or @others