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

is it option C?

---

yes please explain

---

option 1: Its just simulation of TM M₀.  If M₀ accepts the input string, it  belongs to L₁, and if M₀ rejects the input string, it doesnt belong to L1.

So, option 2 only and option 4 eliminated.

option 2: Lets say you have turing machine M and you are simulating it. If M accepts M₀ as input string, then M belongs to L₂. But we dont know how much time it would take for M to accept M₀. It might take infinite time and still not tell if M₀$\in$L(M).

Hence, undecidable

Hence, option A and B both are correct and option C says the same.

---

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