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

Question

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.

Answer 1

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.

---

Edit: I’ll try to address your comments here where I have more space.

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.