Made Easy test series [closed]

Question

• L₁ is recursive language
• L₂ is recursive enumerable language
• Both (a) and (b)
• Both are not recursive enumerable

please give explanation too

Comments

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!

---

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?

---

@Uddipto. For L1, just assume that there exists TM for L1.

Now, if we assume that TM to be M₀, 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 M₀ is exactly the description of M  i.e. M₀ could segregate the strings that represented M by accepting them.

@Pankaj.

Rice theorem is about property languages. I will tell in simple way.

let L_p = {<M> | L(M) = all regular languages }

Here, L_p 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, L_p 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 L_p is undecidable.

---

---

Now compare this with your example. Will you be able to apply Rice theorem? No