2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ The language $L_1$ is not regular (indeed, it is not even recursive). I suggest ignoring this solution. $\endgroup$
    – Yuval Filmus
    Jul 29, 2018 at 17:30
  • 3
    $\begingroup$ Also, from the fact that "Recursively enumerable languages are not closed under complementation" you cannot conclude that "$L′$ is not recursively enumerable." It might or might not be recursively enumerable. $\endgroup$
    – rici
    Jul 29, 2018 at 17:33
  • $\begingroup$ $L=L_1\cap L_2=\{M|M$ accepts exactly 2016 strings$\}$. Both $L$ and $L'$ seems unrecognizable. So options A and D are false. How we can firmly say option option B is also false? Both $L$ and $L'$ seems to be uncountable. Is it enough to say that intersection of uncountable sets is not recognizable and hence option B is false? $\endgroup$
    – RajS
    Jul 29, 2018 at 20:09

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I have some doubt. $L=L_1\cap L_2=\{M|M$ accepts exactly 2016 strings$\}$. Both $L$ and $L'$ seems unrecognizable. So options A and D are false. How we can firmly say option option B is also false? Both $L$ and $L'$ seems to be uncountable. Is it enough to say that intersection of uncountable sets is not recognizable and hence option B is false? $\endgroup$
    – RajS
    Jul 29, 2018 at 20:08
  • $\begingroup$ @anir You're right, (B) is also correct, because the intersection of a language and its complement is ∅. Updated the answer. $\endgroup$
    – Draconis
    Jul 29, 2018 at 20:09
  • $\begingroup$ @Draconis That doesn't seem quite right. $L_1$ and $L_2$ don't look like complements to me, as as anir says, $L_1\cap L_2 =\{M|\text{$M$ accepts exactly 2016 strings}\}$. "at most" and "at least" resp. correspond to $\leq$ and $\geq$, not $\lt$ and $\gt$. Their union is still $\Sigma^*$ (so (C) is correct), but their intersection is not $\varnothing$ (so (B) might not be true). $\endgroup$
    – HTNW
    Jul 30, 2018 at 5:19
  • $\begingroup$ @HTNW Ah, that's the thing: (B) and (C) are asking for the union/intersection of $L$ and $L'$, not of $L_1$ and $L_2$. ($L$ is defined as $L_1 \cap L_2$, that is, Turing machines that accept exactly 2016 strings; it's undecidable and unrecognizable.) $\endgroup$
    – Draconis
    Jul 30, 2018 at 5:28
  • $\begingroup$ @Draconis Ah, that makes sense. $\endgroup$
    – HTNW
    Jul 30, 2018 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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