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 ?

(A) $L$ is recursively enumerable, but is not

(B) $L$ is recursively enumerable, but$ L'$ is not

(C) Both $L$ and $L'$ are recursive

(D) Neither $L$ nor $L'$ is recursively enumerable

Solution[edit]

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 <M,w> using L, just give <M,w,0> and <M,w,1> to two instances of T which is the Turing machine for L. If T accepts the triplet <M,w,0>, it means M halts on w => we have solved halting problem. If T 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, T is bound to stop on at least one of these inputs. 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.

Alternate Solution[edit]

L0 is recursively enumerable. (Given <M,w,0>, we can just give w to M. If M halts on w, <M,w,0> is element of L0.

L1 is not recursively enumerable. Because, halting problem can be solved with it. To decide if a turing machine M accepts a word w, just give <M,w,1> to the Turing machine for L1 and also give w to M. Either M accepts w, or <M,w,1> is accepted by the Turing machine for L1. In either case we have solved halting problem. Hence, L1 is not recursively enumerable.

L1 can be reduced to L0', and hence L0' also is not recursively enumerable.

L1' can be reduced to L0, and hence L1' is recursively enumerable.

Now, L = L0 U L1 = re U not re = not re

L' = (L0 U L1)' =L0' ∩ L1' =not re ∩ re =not re