search
Log In
0 votes
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

in Theory of Computation 123 views
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

Please log in or register to answer this question.

Related questions

0 votes
0 answers
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
asked Dec 1, 2017 in Theory of Computation hem chandra joshi 426 views
2 votes
1 answer
2
410 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)???
asked Oct 6, 2017 in Theory of Computation hs_yadav 410 views
2 votes
1 answer
3
298 views
If we are not able to apply non-monote property ,then is it always true that it is RE but not REC,are there any scenarios where we can't apply non-monotone property but still language is NOT RE. Say,L={TM| L(TM) has atleast one string}, Now it is clearly Language property ... mean theat RE but not REC. P.S:- By (i) and (ii) ,i mean the definitions mentioned here.(http://gatecse.in/rices-theorem/)
asked Jan 22, 2017 in Theory of Computation rahul sharma 5 298 views
2 votes
0 answers
4
215 views
I read this blog http://gatecse.in/rices-theorem/ and I have a doubt in the first property. An example in this blog is L(M) = {0} and it's written that TMno =sigma* . My doubt is how can it be sigma* as sigma* can also contain {0} which should be accepted by TM.
asked Nov 25, 2016 in Theory of Computation Xylene 215 views
...