Q54

MCQ2 marks, −0.5

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 \cup 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

Loading…