2 votes 2 votes closed as a duplicate of: What is the difference ?? L1 is recursive language L2 is recursive enumerable language Both (a) and (b) Both are not recursive enumerable please give explanation too Theory of Computation made-easy-test-series + – Pankaj Joshi asked Jan 31, 2017 • retagged Jun 4, 2017 by Arjun Pankaj Joshi 454 views comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Aboveallplayer commented Jan 31, 2017 reply Follow Share here i have a doubt for L1, what if a string goes into infinite loop! how can we know,if it is going to beaccepted in near future or rjeceted! 0 votes 0 votes Pankaj Joshi commented Jan 31, 2017 reply Follow Share I'm really confused L1= {M | such that M is a TM and M is also recursive} but isn't that undecidable to check a non trivial property of a language? L2 ={M| M accepts languge of M0 where M0 accepts a recursive language} why we are not using rice's theorem and are these interpretations correct? 0 votes 0 votes Sushant Gokhale commented Feb 1, 2017 reply Follow Share @Uddipto. For L1, just assume that there exists TM for L1. Now, if we assume that TM to be M0, then given any input string, it will always halt, right? i.e it will either accpet or reject the string but it will never go into infinite loop. Now, the strings that are accepted by M0 is exactly the description of M i.e. M0 could segregate the strings that represented M by accepting them. @Pankaj. Rice theorem is about property languages. I will tell in simple way. let Lp = {<M> | L(M) = all regular languages } Here, Lp is the property language. Now, what above description says is give me all the turing machine encodings for TM's such that TM accepts regular language. Now, the property of language of TM is that it should be regular. Now, simple thing to do is just make a set and include in that set all languages which should be accepted by TM's. For example I specified, set S = { $\epsilon$, a*, b* ,...} Each element of S is regular language(which is the property here) Now, Lp will contain TM encodings for each element of S. Now, Rice theorem says that if S = {} or S={set of all RE} then this is trivial property else its non-trivial property. If this is non-trivial, then Lp is undecidable. Now compare this with your example. Will you be able to apply Rice theorem? No 0 votes 0 votes Please log in or register to add a comment.