Previous year gate question Toc closed

Question

Define languages L0L0 and L1L1 as follows :

L0={⟨M,w,0⟩∣M halts on w}L0={⟨M,w,0⟩∣M halts on w}

L1={⟨M,w,1⟩∣M does not halts on w}L1={⟨M,w,1⟩∣M does not halts on w}

Here ⟨M,w,i⟩⟨M,w,i⟩ is a triplet, whose first component MM is an encoding of a Turing
Machine, second component ww is a string, and third component ii  is a bit.

Let L=L0∪L1L=L0∪L1. Which of the following is true?

1. L is recursively enumerable, but L′ is not

2.L′ is recursively enumerable, but L is not

3. Both L and L′ are recursive  

4. Neither L nor L′ is recursively enumerable

@srestha @Anu007 @others

As L0 is recursive as it halt

And L1 is recursive enumerable as it does not halt

So recursive U recursive enumerable will recursive enumerable rt?

Comments

here L0={⟨M,w,0⟩∣M halts on w}L0={⟨M,w,0⟩∣M halts on w} doesn't mean that L0 is recursive ....here L0 is encoding of M(halting).....

according to rice theorem :-

L0 is undecidable but L1 decidable therefor ....L0UL1 is Recursive enumerable language????

---

@hs_yadav

here rice's theorem can not be applied, because rice's theorem is applied on a property of language, but here property of machine is given.

neither above language nor its complement is recursively enumerable.

refer this ->https://gateoverflow.in/355/gate2003-54