# Why is $L=\{\langle M \rangle \mid |L(M)| \geq k\}$ not recognizable?

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.

• 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$? – chi Jun 6 '17 at 13:31
• 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. – Sid Caroline Jun 6 '17 at 13:41
• 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. – chi Jun 6 '17 at 14:45
• Your language is indeed recognizable. What is the actual question you are trying to solve? – Yuval Filmus Jun 6 '17 at 15:09
• 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. – Sid Caroline Jun 6 '17 at 19:26