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.

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.

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 $L′$ is not
B. $L′$ is recursively enumerable, but $L$ is not
C. Both $L$ and $L′$ are recursive
D. Neither $L$ nor $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.

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.