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.


1 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.

  • $\begingroup$ I didnt get your rearrangement. Are you doing (A+B)(C+D)=AD+BC ? If yes, is it valid? My main doubt is somewhat different. Union of halting and non halting problem is recursive. Then how just adding a bit to both of them make their union not recursive? $\endgroup$
    – Rnj
    Commented Jan 21, 2020 at 12:41
  • $\begingroup$ I'm applying the distributivity of $\vee$ over $\wedge$, but I eliminate the contradicting cases, such as $b=1\wedge b=0$. The second thing you wrote doesn't make sense. There is no such thing as a "halting language", and the union of a recognizable language and a non-recognizable language (if that's what you mean) can be anything -- either recognizable or not, depends on the languages. $\endgroup$
    – Shaull
    Commented Jan 21, 2020 at 12:43
  • $\begingroup$ This answer proves union of halting and non halting problem is decidable. I was asking whether $L_0\cup L_1$ is also decidable. If not, why? especially because they look very similar to halting and not halting problems, respectively. $\endgroup$
    – Rnj
    Commented Jan 21, 2020 at 12:48
  • $\begingroup$ Well, these are different problems. The bit at the end makes a big difference. It makes it sort of a "disjoint union" rather than a standard union, which means that even after the union, you can tell which word comes from which language, as opposed to the question you linked to. $\endgroup$
    – Shaull
    Commented Jan 21, 2020 at 13:10
  • 1
    $\begingroup$ Yes, exactly. The bit makes this union "artificial". Perhaps think about it this way: suppose the halting problem is a white puzzle-piece, with a weird shape (i.e. a difficult problem). The non-halting problem is the complement white piece, which is also weird. But when you join them, you get a nice rectangle (i.e. an easy problem). However, when you have the extra bit, these pieces have different colors, so while you get a rectangle, it is not nice, and you can tell which piece is which. $\endgroup$
    – Shaull
    Commented Jan 22, 2020 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.