View source for GATE2003 q54 ← GATE2003 q54

Define languages L0 and L1 as follows : $L0 = {< M, w, 0 > | M halts on w} $ $L1 = {< M, w, 1 > | M does not halts on w}$ Here $< M, w, i >$ is a triplet, whose first component. $M$ is an encoding of a Turing Machine, second component,$ w$, is a string, and third component, $i$, is a bit. Let $L = L0 ∪ L1$. Which of the following is true ?

1) $L$ is recursively enumerable, but 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

Both L and L' are undecidable. Because halting problem can be solved with both L and L'.

Halting problem can be stated as follows: A machine M and a word w are given. You have to tell, if M halts on w.

So, to solve halting problem using L, just put a 0 and 1 at the end and give it to L. If L accepts the triplet <M,w,0>, it means M halts on w => we have solved halting problem. If L accepts the triplet <M,w,1>, it means M doesn't halt on w => we have solved halting problem. We know either <M,w,0> or <M,w,1> is in L. So, if L is recursively enumerable, it's bound to stop on at least one of the input. Hence, using L we can solve halting problem => L is not recursively enumerable.

Similarly, we can also show that halting problem can be solved with L'.

Hence, neither L nor L' is recursively enumerable.