# Is the union Non Recursively enumerable?

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

$L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\}$

$L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts on }w\}$

Here $\langle M, w, i \rangle$ 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?

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

I know that $L_0$ is recursively enumerable and $L_1$ is non recursively enumerable but their union is what I'm confused with .

I'm not sure though, but I am unable to design TM for $L$ which makes me think that it is not recursively enumerable ?

• What is $L'$? The complement of $L$? – Andrej Bauer Jul 13 '17 at 7:37
• Hint: if $L$ is r.e., can you solve the halting problem then? – Andrej Bauer Jul 13 '17 at 7:38
• @AndrejBauer yes, L' is the complement of L. – Garrick Jul 13 '17 at 7:39
• @chi We have not yet studied reduction. – Garrick Jul 13 '17 at 7:41
• A hint is not supposed to be immediately obvious. Let me walk over to the institute, and you think about it some more, ok? – Andrej Bauer Jul 13 '17 at 7:43