The Gateway to Computer Science Excellence
0 votes
67 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 by Loyal (7.8k points) | 67 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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
198,227 comments
104,909 users