# Why is the intersection of these two Languages Recursively Enumerable, not Recursive?

I am only several days exposed to computational theory, so my understanding is quite slim: in a question, it says that for a regular language L1 and a recursively enumerable but not recursive language L3, L3 ∩ L1 is recursively enumerable. But I thought it would be recursive?

Now, the text and I came to the same first conclusion - that it is important to deduce that L1 is a recursive language, since it is regular, and go from there - but my understanding is that if a recursive language had an undecideable intersected, you'll either get the empty set (which is recursive) or you'll get a set of elements common to both. Since all elements in a recursive must lead to halting, then the elements of the intersection all must lead to halting.

Hence '(recursive) ∩ (rec enu but not recursive)' and so 'L1 ∩ L3' should be recursive?

I must have gone wrong somewhere because the text, without explanation, just says it's recursively enumerable - where have I gone wrong? Thanks for your insight.

• "for a regular language L1 and a recursively enumerable but not recursive language L3, L3 ∩ L1 is recursively enumerable" -- be wary of the difference "is always r.e." or "is sometimes r.e." here. I suspect that you mean the second and the first one isn't true. – Raphael May 5 '18 at 18:31
• Since $\Sigma^*$ (the language of all words) is recursive (even regular!), intersecting it with any language $L$ can't "promote" $L$ from non-recursive to recursive. – Yuval Filmus May 5 '18 at 20:08

Let $L_1$ be the full language. Certainly, $L_3 \cap L_1 = L_3$, which by assumption is not recursive.

I didn’t fully follow your reasoning in the second paragraph, but you might want to think some more about which Turing machine “must lead to halting” refers to. In particular, a Turing machine for our $L_1$ will halt on every string, but this does not tell you that any subset of the full language is recursive.

We are dealing with a double set structure: At the lowermost level, we have words. Languages are set of words, but we are also talking about sets of languages, i.e., sets of sets of words, such as the set of regular languages. The relationship between regular, recursively enumerable and recursive languages happens on the upper level: Let $L$ be any regular language, which means that it is accepted by a finite automaton $\mathcal{A}$. Because every finite automaton $\mathcal{A}$ can be implemented as a Turing machine $\mathcal{M}$, we know that $L$ must also be a recursive language. Since every such element $L$ of the set of regular languages is an element of the set of recursive languages, the former is a subset of the latter.
This does not mean much on the level of individual words. Let’s again take the language $L_1 := \Sigma^*$ of all words. This language is decided by the Turing Machine $\mathcal{M}_1$ that always accepts. Thus, $L_1$ is in the set of recursive languages and every word “leads to halting” for the specific machine $\mathcal{M}_1$. Now let us consider the language $L_3$ of Turing machines that terminate on the empty input. It can be accepted by a universal Turing Machine $\mathcal{M}_3$, so the language is recursively enumerable (and we know that it is not recursive). Sure, every word in the intersection of $L_1$ and $L_3$ will make both $\mathcal{M}_1$ and $\mathcal{M}_3$ terminate and accept.
But how do you build a single Turing machine from that that still accepts the intersection and will reject everything else? The first attempt would be to simulate both Turing machines and accept if both accept. As soon as one rejects, you reject. Indeed, this machine accepts the intersection and proves that the intersection is recursively enumerable. But if $\mathcal{M}_1$ accepts and $\mathcal{M}_3$ diverges, your machine will also diverge. To reject, you would have to figure out in finite time whether $\mathcal{M}_3$ is diverging on the current input or just takes a long time to accept. This is not possible to do for all inputs.
• The converse is true: If $L_1 \cap L_3 = L_3$, then everything in $L_3$ is already in $L_1$, so $L_3$ is a subset of $L_1$. It seems to me that you are confused between a set of languages being contained in another and a language being contained in another. The set of recursive languages is contained in the set of rec. enum. languages because every recursive language is rec. enum. The full language $\Sigma^*$ is recursive and is only contained in itself (it already contains all words), so it is not contained in any non-recursive language. This also gives a counterexample to your next proposal. – Paul May 5 '18 at 21:01