Multiple choice

Define languages L0 and L1 as follows: L0 = {<M, w, 0> | M halts on w} L1 = {<M, w, 1> | M 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 = L0$\cup$L1. Which of the following is true?

  1. L is recursively enumerable, but $\bar L$ is not
  2. $\bar L$ is recursively enumerable, but L is not
  3. Both L and $\bar L$ are recursive
  4. Neither L nor $\bar L$ is recursively enumerable
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Keep practicing — related questions