3
$\begingroup$

Consider these 2 languages:

  • $L_{\ge5} = \left \{ \left< M \right> : M \text{ accepts at least 5 strings} \right\} $

  • $L_{<5} = \left \{ \left< M \right> : 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< M \right> :L(M)= \emptyset \right \} \notin L_{\ge5} $ and $L_{\ge5}$ are not empty. For example, I define $L= \left \{ \left< M \right> : 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< M \right>: L(M)= \emptyset \right\} \in L_{<5}$ and $L=\left\{ \left< M \right>:M \text{ accepts all palindromes} \right\} \notin L_{<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?

$\endgroup$
4
$\begingroup$

$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_{<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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.