Here $M$ denotes a turing machine.

By set theory, $L = \overline{E_{TM}} \cap \overline{L_0} \cap \overline{L_1}$ where $L_i=\{\langle M \rangle \mid |L(M)|=i\}$. And I know that $\overline{E_{TM}}$ is recognizable.

That is about all I know at this point. I suppose I need to use mapping reducibility to prove $L$ is not recognizable, but am not sure how.

  • 2
    $\begingroup$ The $L$ in the title looks as r.e. (recognizable) to me. A semidecider can be defined using some dovetailing, as far as I can see. By the way, what is $E_{TM}$? Empty-language TMs? Why your alternative definition in the text for $L$ does not use $k$? $\endgroup$ – chi Jun 6 '17 at 13:31
  • $\begingroup$ Yes $E_{TM}$ denotes the set of turing machines $M$ with $L(M)$ empty. And yes I forgot to include $L_2$, $L_3$,...,$L_{k-1}$ in my expression, but you get the idea. $\endgroup$ – Sid Caroline Jun 6 '17 at 13:41
  • $\begingroup$ Now I see what you mean, thanks. Note that we have $E_{TM} = L_0$, so there's some redundancy in your expression. Still, I still think $L$ is recognizable. $\endgroup$ – chi Jun 6 '17 at 14:45
  • 2
    $\begingroup$ Your language is indeed recognizable. What is the actual question you are trying to solve? $\endgroup$ – Yuval Filmus Jun 6 '17 at 15:09
  • $\begingroup$ Are you absolutely sure? Because I've seen a similar example $L_k = \{ \langle M \rangle \mid |L(M)| = k \}$ which is neither recognizable nor co-recognizable. $\endgroup$ – Sid Caroline Jun 6 '17 at 19:26

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.