The Gateway to Computer Science Excellence

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,227 comments

104,909 users