Union of R.E. and Non R.E. language Let 
\begin{align*}
    L_1 &amp;=\{\langle M,w\rangle \mid M\text{ halts on }w\}\\
    L_2 &amp;=\{\langle M,w\rangle \mid M\text{ does not halt on }w\}\,.
\end{align*}
Here $M$ represents encoding of a Turing machine (T.M.) and $w$ is the input string. What is the class of $L=L_1 \cup L_2$?



I read that the union would be a regular language as a string has to belong to either $L_1$ or $L_2$ (i.e., halt or not halt) so their union would be a regular language.

I have a doubt. Suppose we assume $L$ as a recursively enumerable (R.E.) language then there exists a T.M. which halts on all "yes" cases. Here yes cases means strings which belong to either $L_1$ or $L_2$.
So, if a string belongs to $L_2$, then the T.M. should halt which means that we are able to halt and say "yes" even if machine doesn't halt on this string (according to condition of $L_2$). This solves halting problem and hence assumption is not correct and so $L$ should be non recursively enumerable. 

I know that there is some flaw in the explanation given above but I am not able to find it.

Can someone please help me?
The language $L = L_1 \cup L_2$ consists of all pairs $\langle M,w \rangle$ where $M$ is a description of a Turing machine and $w$ is a word. This language is not necessarily regular (it depends on the exact encoding), but it is certainly decidable. All you have to do, given an input, is to decide whether it is of the form $\langle M,w \rangle$.

Note that deciding $L$ bears no relation to the halting problem. My description of $L$ doesn't refer to whether $M$ halts on $w$ or not. Here is a similar example. Let $f$ be an uncomputable integer-valued function. The function $g := 1-f$ is uncomputable as well, yet $f + g$ is computable.