Define languages L0 and L1 as follows : L0 = {< M, w, 0 > | M halts on w} L1 =…

GATE · 2003 · CS

Define languages L0 and L1 as follows :

L0 = {< M, w, 0 > | M halts on w}
L1 = {< M, w, 1 > | M does not halts 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 = L0 ∪ L1. 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

Attempted by 35 students.

Explore the full course: Gate Guidance By Sanchit Sir