Determining if given languages are regular or recursively enumerable

Question

I came across following problem:

Suppose $L_1$ and $L_2$ are two languages, $M$ is a Turing machine
$L_1 =\{M|M$ accepts at most 2016 strings$\}$
$L_2=\{M|M$ accepts at least 2016 strings$\}$
If $L=L_1\cap L_2$, then which one of the below is correct?
A) $L'$ is recursively enumerable
B) $L\cap L'$ is recursively enumerable
C) $L\cup L'$ is recursively enumerable
D) $L$ is recursively enumerable

The solution given was:

$L_1$ by definition is regular language (“atmost”). $L_2$ by definition is recursively enumerable (“at least”). Recursively enumerable languages are closed under regular intersection. Hence, $L = L_1 ∩ L_2$ is recursively enumerable. Thus option D. Recursively enumerable languages are not closed under complementation. Hence $L’$ is not recursively enumerable. Hence option A is wrong. And since $L’$ is not recursively enumerable, options B and C are also wrong.

My doubt

I am struggling with how $L_1$ is regular and $L_2$ is recursively enumerable, that is with first two sentences:

$L_1$ by definition is regular language (“atmost”). $L_2$ by definition is recursively enumerable (“at least”).

Usually language definition specifies criteria on format of input string which will allow us to reject or accept it. But here the definition specifies how many strings the language has or its corresponding Turing machine accepts.

I found this similar sounding problem, in which the answer gives membership algorithm and hence proving language in that problem is indeed recursively enumerable. But I feel this does not applies in my problem. Correct? Or the problem is incorrect in telling number of strings languages can accept instead of format of acceptable strings?

Answer 1

Your intuition is entirely correct; this solution is nonsense. $L_1$ isn't a regular language; it's not even a decidable language, by Rice's Theorem, and also not recognizable (aka recursively enumerable).

$L_2$ is in fact recognizable. The following algorithm recognizes it:

Take an encoded Turing machine $M$ as input. First simulate it on every input of length ≤ 1 for 1 step, then on every input of length ≤ 2 for 2 steps, and so on. Keep track of how many distinct inputs it's ever accepted. If this number ever exceeds 2016, return True.

But as it turns out, none of this matters to the actual problem. Note that (C) is taking the union of a language with its complement, and the union of any language with its complement is $\Sigma^*$. This language is regular, thus decidable, thus recognizable. So the correct answer is (C).

EDIT: Of course, the intersection of a language with its complement is $\varnothing$, which is also regular, thus decidable, thus recognizable. So (B) is also true.