Union of halting-like problem and non-halting-like problem

Question

I came across the following problem:

Define languages $L_0$ and $L_1$ as follows :

$L_0=\{⟨M,w,0⟩∣M\text{ halts on }w\}$
$L_1=\{⟨M,w,1⟩∣M\text{ does not halt 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=L_0∪L_1$. Which of the following is true?

A. $L$ is recursively enumerable, but $\overline{L}$ is not
B. $\overline{L}$ is recursively enumerable, but $L$ is not
C. Both $L$ and $\overline{L}$ are recursive
D. Neither $L$ nor $\overline{L}$ is recursively enumerable

I first felt that despite the bit as a third member of triple, $L_0$ is still equivalent to halting problem and $L_1$ is non halting problem. Union of halting and non halting problem is recursive as can be seen here. So, same will apply to the languages in the problem and their union will also be recursive, that is option C. But the answer given was D. So am guessing if its correct or not. I was not able to guess how that extra bit in the triple makes it different from halting problem.

Answer 1

Let's write formally what $L$ and $\overline{L}$ are:

$$L=\{\langle M,w,b \rangle| (b=0 \wedge M(w) \mbox{ halts}) \vee (b=1 \wedge M(w) \mbox{ does not halt}) \}$$

$$\overline{L}=\{\langle M,w,b \rangle| (b=1 \vee M(w) \mbox{ does not halt}) \wedge (b=0 \vee M(w) \mbox{ halts}) \}$$ The latter is confusing, so let's rearrange it:

$$\overline{L}=\{\langle M,w,b \rangle| (b=1 \wedge M(w) \mbox{ halts}) \vee (b=0 \wedge M(w) \mbox{ does not halt}) \}$$

(Note that we ignore malformed inputs, but that can be easily circumvented and does not effect the answer).

From this, you can easily see that $L$ and $\overline{L}$ are basically the same idea -- the bit at the end determines whether you're looking at the halting problem or at its complement. In either case, neither $L$ nor its complement are recursively enumerable.

One thing that can trigger you to suspect this is the answer, even without formally writing $\overline{L}$, is the fact that both the halting problem and its complement easily reduce to $L$. Thus, $L$ is not recongnizable nor co-recognizable, and so neither is its complement.