0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ "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. $\endgroup$ – Raphael♦ May 5 '18 at 18:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 5 '18 at 20:08
1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Ah right, ok. I'll try and understand as to why that is (I'm unfortunately extremely new to this) - if L1 n L3 = L3, is L1 a subset of L3, then? In particular, are all recursive languages a subset of (or a sublanguage of?) rec enu languages, even those rec enu that aren't also recursive/decidable? In turn, are all rec enu languages subsets (sublanguages) of undecidable languages, meaning if L4 were undecidable, L4 n L1 = L4? If that's the case, I'm thinking that also L4 u L1 would be a recursively enumerable language, having both halting and non halting elements? Thanks so much for your help! $\endgroup$ – TheRealPaulMcCartney May 5 '18 at 19:05
  • $\begingroup$ 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. $\endgroup$ – Paul May 5 '18 at 21:01
  • $\begingroup$ I’m having trouble following your next points. Note that you cannot determine whether a language is recursive by looking at its words in isolation without fixing a Turing Machine. A language is not undecidable because it contains “hard” words (every word can be recognized by a TM), but by being too “rugged” of a set such that one single TM is not enough to determine for every word if it is in the language or its complement. Does that help? $\endgroup$ – Paul May 5 '18 at 21:12
  • $\begingroup$ Thank you, the last comment helped the most, but I've still got a way to go. I think I'm indeed confused as to the difference between a language being contained in another, and a set of languages or rather set of strings from a language being a subset of sets of other languages or strings. $\endgroup$ – TheRealPaulMcCartney May 7 '18 at 9:38
  • $\begingroup$ I'll explain my reasoning as to the above: I understood all the words of a regular language (L1) and so the language itself, to be a subset of of higher languages, including regular languages, exactly like how the set of naturals is a subset of the reals(I think this is where I went wrong according to your first answer, tho I don't yet understand what the correct thinking is). Now, if you're taking L1 n L3, since L3 is r.e. but not recursive, it contains halting and non halting words (this where I went wrong again according to your second answer) then anything common to both L's will be... $\endgroup$ – TheRealPaulMcCartney May 7 '18 at 9:43

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.