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 ∪ L_1$. Which of the following is true?

  1. $L$ is recursively enumerable, but $L'$ is not

  2. $L'$ is recursively enumerable, but $ L$ is not

  3. Both $L$ and $L'$ are recursive  

  4. Neither $L$ nor $L'$ is recursively enumerable

I know that $L_0$ is recursively enumerable and $L_1$ is non recursively enumerable but their union is what I'm confused with .

I'm not sure though, but I am unable to design TM for $L$ which makes me think that it is not recursively enumerable ?

  • $\begingroup$ What is $L'$? The complement of $L$? $\endgroup$ – Andrej Bauer Jul 13 '17 at 7:37
  • $\begingroup$ Hint: if $L$ is r.e., can you solve the halting problem then? $\endgroup$ – Andrej Bauer Jul 13 '17 at 7:38
  • $\begingroup$ @AndrejBauer yes, L' is the complement of L. $\endgroup$ – Garrick Jul 13 '17 at 7:39
  • 1
    $\begingroup$ @chi We have not yet studied reduction. $\endgroup$ – Garrick Jul 13 '17 at 7:41
  • 2
    $\begingroup$ A hint is not supposed to be immediately obvious. Let me walk over to the institute, and you think about it some more, ok? $\endgroup$ – Andrej Bauer Jul 13 '17 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.