GATE CS 2003 Q54 — Undecidability

To determine the status of the language $L = L_0 \cup L_1$ and its complement $L'$, let us analyze their properties using reductions from the halting problem and its complement.

Recall the definition of the Halting Language ($H$) and its complement ($H^c$):

• $H = \{\langle M, w \rangle \mid M \text{ halts on } w\}$ (Recursively Enumerable (RE), but not Recursive)
• $H^c = \{\langle M, w \rangle \mid M \text{ does not halt on } w\}$ (Not Recursively Enumerable)

1. Analyzing $L$

By definition, a triplet $\langle M, w, i \rangle \in L$ if and only if:

• $i = 0$ and $M$ halts on $w$, OR
• $i = 1$ and $M$ does not halt on $w$.

We can reduce the non-halting problem $H^c$ to $L$ using a mapping reduction $f(\langle M, w \rangle) = \langle M, w, 1 \rangle$:

Since $H^c \le_m L$ and $H^c$ is not recursively enumerable, $L$ is not recursively enumerable.

2. Analyzing $L'$

The complement language $L'$ contains all strings that are either malformed (which is a recursive set and does not affect RE-ness) or triplets $\langle M, w, i \rangle$ such that:

• $i = 0$ and $M$ does not halt on $w$, OR
• $i = 1$ and $M$ halts on $w$.

We can reduce the non-halting problem $H^c$ to $L'$ using a mapping reduction $g(\langle M, w \rangle) = \langle M, w, 0 \rangle$:

Since $H^c \le_m L'$ and $H^c$ is not recursively enumerable, $L'$ is not recursively enumerable.

Conclusion

Since neither $L$ nor $L'$ is recursively enumerable, the correct option is D.