Show that a language is RE or recursive Consider these 2 languages:



  $L_{\ge5} = \left \{ \left&lt; M \right&gt; : M \text{ accepts at least 5 strings} \right\} $


  $L_{&lt;5} =  \left \{ \left&lt; M \right&gt; : M \text{ accepts fewer than 5 strings} \right\}$



Are these recursive, R.E., or not R.E. sets (languages)?

I would say that they are not recursive, based on applications of Rice's Theorem.


For the first case $L_{e}= \left \{ \left&lt; M \right&gt; :L(M)= \emptyset \right \} \notin L_{\ge5} $ and $L_{\ge5}$ are not empty. For example, I define $L= \left \{ \left&lt; M \right&gt; : M \text{ accepts all palindromes} \right \}$, which is not finite set and accepts an infinite number of strings.
For the second case I would do the same thing. I have $L_{e}=\left\{ \left&lt; M \right&gt;: L(M)= \emptyset \right\} \in L_{&lt;5}$ and $L=\left\{ \left&lt; M \right&gt;:M \text{ accepts all palindromes} \right\} \notin L_{&lt;5} $


So I would say that both are not recursive. Is my reasoning correct?

Now about the R.E. of the languages I don't have an idea of how I can prove it, this should be the beginning (if L is not RE it can't be recursive), how can I check if they are RE or not?

From the definition: "$L$ is RE $\iff$ there exists a TM $M$ that accepts $L$", so I just have to define a TM that accepts each language?
$L_{\geq5}$ is RE. Basically, given a machine $M$, you iterate through all strings, starting with all of length 0, then length 1, etc. You simulate $M$ and test if the current string $s$ is accepted by $M$. If it is, then you increment some counter. If the counter ever hits 5, you accept. There's no guarantee that this will terminate, which is why it's RE and not recursive. There is a guarantee, however, that it will terminate for any input machine $M$ that does accept 5  or more strings.

We know from Rice's theorem that $L_{\geq5}$ is not recursive, and since it is RE, then we know its compliment is not RE. So $L_{&lt;5}$ is neither RE or recursive.

Intuitively, you could iterate through all strings, but there would never be a point where you could say "Based on the strings I've seen so far, I know that this machine accepts less than 5 strings." Even if you accept less than 5 so far, there's no way of knowing that there aren't larger strings which would be accepted.