Multiple choice

Define languages L0 and L1 as follows: L0 = {M, w, 0 > 1 M halts on w} L0 = {M, w, 0 > 1 M does not halts on w} Here < M, u, 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
A Correct answer
Explanation

null

Keep practicing — related questions