Define languages L0 and L1 as follows : L0 = {< M, w, 0 > | M halts on w} L1 =…
2003
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 6 students.
Show answer & explanation
Correct answer: D
L0 is the halting problem for Turing machines, which is recursively enumerable but not recursive. L1 is its complement, which is not recursively enumerable. The union L = L0 ∪ L1 includes all valid encodings of <M, w, i>, but since L1 is not recursively enumerable, L cannot be recursively enumerable. The complement L' would also fail to be recursively enumerable because L is not recursive and its complement cannot be enumerated. Thus, neither L nor L' is recursively enumerable.