Questions: Properties of Recursively Enumerable Languages

Question 1

Suppose L₁ and L₂ are both recursively enumerable but neither is decidable. Which of the following is guaranteed to also be recursively enumerable?

• A. The complement of L₁
• B. L₁ minus L₂ (strings in L₁ but not in L₂)
• C. L₁ intersected with L₂
• D. L₁ symmetric difference with L₂

Answer: (C)

RE is closed under intersection. If M₁ semi-decides L₁ and M₂ semi-decides L₂, running both in parallel and accepting only when both accept semi-decides L₁ ∩ L₂. This works because acceptance is a positive event you can detect. RE is NOT closed under complement (option A), set difference (option B — L₁ \ L₂ = L₁ ∩ co-L₂, and co-L₂ may not be RE), or symmetric difference (option D — which involves complements). Only union and intersection preserve RE membership.

Question 2

Why does the dovetailing argument that works for RE union fail when applied to complement?

• A. Dovetailing requires both machines to eventually halt, which they may not do for languages in RE
• B. To semi-decide the complement, you need to accept strings not in L, but you can only recognize non-acceptance if the machine halts and rejects — you cannot detect an infinite loop as a positive event
• C. Dovetailing works for complement too; the problem is that complement is not preserved under parallel composition
• D. The complement construction requires deterministic machines, but dovetailing only works for nondeterministic machines

Answer: (B)

For union, dovetailing works because acceptance is a positive event you can detect when it happens — if either machine accepts, accept. For complement, you need to recognize strings NOT in L. But 'not accepted by M' has two causes: M rejects (detectable) or M loops forever (undetectable). You cannot observe a non-halting loop as a positive event — you would have to wait forever to confirm it. There is no computational signal that tells you 'this machine will never halt,' which is precisely why the halting problem's complement is not RE.

Question 3

A language L is decidable if and only if both L and its complement are recursively enumerable.

• T. True
• F. False

Answer: True

This is the characterization RE ∩ co-RE = decidable. If L is decidable, a machine that always halts witnesses both L and co-L as semi-decidable. Conversely, if both L and co-L are RE (say, semi-decided by M and M'), run both in parallel. Every input is in either L or co-L, so exactly one of M or M' will eventually accept. When one accepts, halt. This gives a decider. The argument crucially uses that one of them will halt — you just don't know which one will go first.

Question 4

Since RE is closed under both union and intersection, it follows by De Morgan's laws that RE is expected to also be closed under complement.

• T. True
• F. False

Answer: False

De Morgan's laws apply to sets but don't transfer computational closure properties. RE closure under union and intersection does not imply closure under complement because the complement of an RE language is not necessarily RE — it may be in co-RE but not RE itself. If RE were closed under complement, then every RE language would be decidable (run the RE machine and the co-RE machine in parallel; one will halt), which would mean RE = co-RE = decidable, contradicting the undecidability of the halting problem.

Question 5

Explain why the inability to detect non-termination is the fundamental barrier to RE closure under complement.

Model answer: A Turing machine M semi-decides L: it halts and accepts on every string in L, but on strings not in L it either halts-and-rejects or loops forever. To semi-decide the complement co-L, you need a machine that accepts exactly the strings M does NOT accept. But 'M does not accept x' could mean M halts-and-rejects (detectable) or M runs forever (undetectable). There is no finite computation that can distinguish 'M will reject at step 10,000' from 'M will loop for all eternity' — both look the same up to any finite number of steps. You cannot convert non-acceptance into acceptance without solving the halting problem.

The asymmetry is fundamental: acceptance is observable (you see the 'accept' event) but non-acceptance by a non-halting machine is not observable (you see nothing, forever). RE captures exactly the 'verifiable' languages — you can verify membership by running long enough to see an accept. Closing under complement would require verifying non-membership, which requires detecting infinite loops, which the halting problem shows is impossible.