# Is the below language Non R.E?

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

$L_1=\{⟨M,w,1⟩\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 \cup L_1$. Is $L$ non R.E ?

After seeing the question I was able to figure out that there are some strings that do not belong to $L_0$ as well as $L_1$.

Like, lets take the case for $L_0$ and a string $001\dots10−01−1$, ("$-$" shown for notation purpose only) where the  first component describes a TM $M$ followed by input "$w=01$" and last bit "$1$". Now suppose M halts on "$01$". Still the given input is not in $L_0$ as the last bit is "$1$" and not "$0$" as required by $L_0$. So, this input must be in $L_1$. But since $M$ halts on $w$, this input is not in $L_1$ either.  So there are infinite strings like these. I am not able to prove that these infinite set of strings are not r.e.

Is there any method to solve these kind of problems? I am not able to master these kind of problems.

• The method to solve this kind of problem is to solve a few of these exercises. We can solve each given exercise for you, but you will never understand the material until you struggle with it on your own. – Yuval Filmus Sep 6 '17 at 13:12
• For some of the problems I am finding it hard to reduce it to halting problem :( – Zephyr Sep 6 '17 at 13:21
• Hint: Assume that $L$ is r.e. and $M_L$ recognizes $L$. Given $M, w$, $M$ on $w$ either halts or not. This means that either $\langle M, w, 0 \rangle$ or $\langle M, w, 1 \rangle$ must be in in $L$. Then ... recall what a r.e. set means, and think about how you could run/simulate $M_L$ on both input $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$ simultaneously. – fade2black Sep 6 '17 at 19:44
• @fade2black, Actually I did the same thing to other problem slightly different than this and I got confused there. You can see the link here :- cs.stackexchange.com/questions/80892/… – Zephyr Sep 6 '17 at 19:46

Assume that $L$ is r.e. and $M_L$ recognizes $L$. Given $\langle M,w \rangle$, $M$ on $w$ either halts or not. This means that either $\langle M, w, 0 \rangle$ or $\langle M, w, 1 \rangle$ must be in $L$. Then using a universal Turing machine start to run/simulate $M_L$ on both inputs $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$, simultaneously, say one step at a time for each input. After each step check if $M_L$ halts on at least one input. Since $L$ is r.e. and exactly one of $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$ belongs to $L$, $M_L$ must eventually halt on one of them. Depending on which input $M_L$ halts, you can tell if $M$ halts on $w$. This decides the Halting problem and hence $L$ is not r.e.
• That language is quite different from this one. Pay attention to additional 0 and 1s in this case. That one is decidable and mainly about encoding rather than halting. The third bit bears information about halting of $M$ on $w$. That's why we can reduce the HP to $L$ in case $L$ is r.e. – fade2black Sep 6 '17 at 20:50
• Right, since $L$ is the union, you cannot tell which one $\langle M,w \rangle$ belongs to. In fact $L_1 \cup L_2$ in that question is the set of all TMs. – fade2black Sep 6 '17 at 21:18
The Turing machine $M$ doesn't halt on $w$ if and only if $\langle M,w,1 \rangle \in L$. This shows that $L$ is not r.e.: if it were, then since the halting problem is r.e., we would get a decision procedure for the halting problem. Similarly, $L$ is not co-r.e.