Turing Machine

Question

L1={<M>| M is a Turing Machine , P is a TM that halts on all input, and P$\epsilon$L(M)}

L2={<M>| M is a Turing Machine , P is a TM that halts on all input, and M$\epsilon$L(P)}

Which one REC, or RE or non RE ?

Comments

l₁ is Re and l₂ is Rec

---

explain plz:)

---

L₂={<M>| M is a Turing Machine, P is a TM that halts on all input, and MϵL(P)}

i.e. p is halting turing machine, i.e. M always halt and say sting belongs to that or not,

L₁={<M>| M is a Turing Machine, P is a TM that halts on all input, and PϵL(M)}

here machine halt if string belongs otherwise in loop.

---

@Anu007 can you please tell about L2 using Rice's theorem??

---

L2 is REC means decidable means trivial property.So,you cannot apply Rices theorem here.Also,it can be applied if it is on L(M) but in l2 it is on L(P)

---

L2 is REC. Basically, all the members of L2 belong to the set L(P) (as it is given in the question) which means it consists of all halting turing machines. So it is very analogous to asking whether Halting Turing Machines fall under REC, which is actually trivial. Hence we conclude L2 is REC.

However I'm not sure about L1.

Answer 1

For L1:  Since PϵL(M) means any string from P, Does it belong to L(M) ?

now there arises two cases,if there is a string which is accepted by M , it will say YES .

If not, then it wud halt or fall into infinite loop ,we cant say..   therefore L1 is RE.

For L2:  (Its more easy) Since P is a Halting TM (as given halts on all input),

it is always decidable that a string from  M belongs to P or not . It can say YES or NO. (as it halts on every input).

therefore, L2 is REC.