Closure Properties of Recursive and RE Languages

Hello! Welcome back to our study of computability.

In our previous lesson, we established the fundamental distinction between recursive (decidable) languages and recursively enumerable (RE) languages. We learned that for a recursive language, a Turing Machine (TM) must halt on every input, providing a clear "yes" or "no." For an RE language, the TM is only guaranteed to halt and accept for strings in the language. We also saw that this distinction is captured by Post's Theorem: a language $L$ is recursive if and only if both $L$ and its complement $L^{c}$ are RE.

Today, we will build upon these definitions to explore their closure properties. This lesson addresses the learning outcome: Prove closure properties of recursive and RE languages under union and intersection. We will investigate whether combining languages from these classes, using operations like union and intersection, results in a language that is still in the same class. Understanding these properties is crucial for knowing how we can construct complex computable languages from simpler ones.

1. Closure Under Union

Let's start with the union operation. Given two languages, $L_{1}$ and $L_{2}$ , from the same class, is their union $L_{1} \cup L_{2}$ also in that class?

Recursive Languages are Closed Under Union

Let $L_{1}$ and $L_{2}$ be two recursive languages. By definition, there exist Turing Machines $M_{1}$ and $M_{2}$ that are deciders for them. This means $M_{1}$ and $M_{2}$ are guaranteed to halt on any input.

To prove closure, we need to construct a new TM, let's call it $M_{u ni o n}$ , that decides $L_{1} \cup L_{2}$ . The construction is straightforward:

Construction of $M_{u ni o n}$ for an input string w:

Run the decider $M_{1}$ on input w.
Since $M_{1}$ is a decider, it is guaranteed to halt.
- If $M_{1}$ accepts w, then w is in $L_{1}$ , so it must be in $L_{1} \cup L_{2}$ . $M_{u ni o n}$ accepts and halts.
- If $M_{1}$ rejects w, proceed to the next step.
Run the decider $M_{2}$ on input w.
Since $M_{2}$ is a decider, it is guaranteed to halt.
- If $M_{2}$ accepts w, then w is in $L_{2}$ , so it must be in $L_{1} \cup L_{2}$ . $M_{u ni o n}$ accepts and halts.
- If $M_{2}$ rejects w, then w is in neither $L_{1}$ nor $L_{2}$ . $M_{u ni o n}$ rejects and halts.

This sequential execution works because we have the guarantee that both $M_{1}$ and $M_{2}$ will always terminate. Therefore, $M_{u ni o n}$ is a decider, and $L_{1} \cup L_{2}$ is a recursive language.

Closure Property Under Union for Recursive Languages — This diagram illustrates a 2-tape TM construction that decides the union of two recursive languages, L1 and L2. It formalizes the sequential simulation process we just described.

Recursively Enumerable Languages are Closed Under Union

Now, let's consider two RE languages, $L_{1}$ and $L_{2}$ , with corresponding recognizers $R_{1}$ and $R_{2}$ . Can we use the same sequential simulation?

The answer is no. Imagine we have a string w that is not in $L_{1}$ but is in $L_{2}$ . If we run $R_{1}$ on w first, $R_{1}$ might loop forever. Our machine would never get to run $R_{2}$ and discover that w is, in fact, in the union.

The solution is to simulate both machines "in parallel." From your background in building complex systems, you can think of this as a form of time-slicing or cooperative multitasking on a single-tape TM.

Construction of $R_{u ni o n}$ for an input string w:

For $k = 1, 2, 3, \dots$ :
a. Simulate one step of $R_{1}$ on w. If $R_{1}$ accepts, then $R_{u ni o n}$ accepts and halts.
b. Simulate one step of $R_{2}$ on w. If $R_{2}$ accepts, then $R_{u ni o n}$ accepts and halts.

Why does this work?

If $w \in L_{1} \cup L_{2}$ , then either $R_{1}$ or $R_{2}$ (or both) must accept w in a finite number of steps. Our interleaved simulation guarantees that we will eventually execute that accepting step, at which point $R_{u ni o n}$ halts and accepts.
If $w \in / L_{1} \cup L_{2}$ , then neither $R_{1}$ nor $R_{2}$ will accept. $R_{u ni o n}$ will continue to simulate them, potentially looping forever. This is acceptable behavior for a recognizer.

Thus, $R_{u ni o n}$ correctly recognizes $L_{1} \cup L_{2}$ , and the class of RE languages is closed under union.

To see these proofs explained with clear visuals, please watch the following segment.

Closure Properties of Decidable and Turing recognizable languages

This video from the Theory of Computation channel provides a step-by-step proof of closure under union for both decidable (recursive) and Turing-recognizable (RE) languages. It clearly explains the necessity of parallel simulation for RE languages.

Watch the segment from 01:18 to 09:19. Pay close attention to the argument for why sequential simulation fails for Turing-recognizable languages and how simultaneous simulation solves the problem.

2. Closure Under Intersection

Next, we examine the intersection operation. Given $L_{1}$ and $L_{2}$ , is $L_{1} \cap L_{2}$ in the same class?

Recursive Languages are Closed Under Intersection

Let $L_{1}$ and $L_{2}$ be recursive languages with deciders $M_{1}$ and $M_{2}$ . We can construct a decider $M_{in t er sec t}$ for $L_{1} \cap L_{2}$ .

Construction of $M_{in t er sec t}$ for an input string w:

Run the decider $M_{1}$ on w.
If $M_{1}$ rejects, then w cannot be in the intersection. $M_{in t er sec t}$ rejects and halts.
If $M_{1}$ accepts, proceed to the next step.
Run the decider $M_{2}$ on w.
If $M_{2}$ accepts, then w is in both languages. $M_{in t er sec t}$ accepts and halts.
If $M_{2}$ rejects, $M_{in t er sec t}$ rejects and halts.

This works because both machines are guaranteed to halt. The resulting TM, $M_{in t er sec t}$ , is a decider, proving closure.

An alternative, more abstract proof uses De Morgan's laws:
$L_{1} \cap L_{2} = (L_{1}^{c} \cup L_{2}^{c})^{c}$
We know recursive languages are closed under complement (we'll revisit this in a moment) and we just proved they are closed under union. Since $L_{1}^{c}$ and $L_{2}^{c}$ are recursive, their union is recursive, and the complement of that union is also recursive.

Recursively Enumerable Languages are Closed Under Intersection

Let $L_{1}$ and $L_{2}$ be RE languages with recognizers $R_{1}$ and $R_{2}$ . Surprisingly, the simple sequential simulation that failed for union works for intersection.

Construction of $R_{in t er sec t}$ for an input string w:

Run the recognizer $R_{1}$ on w.
If $R_{1}$ halts and accepts, then proceed to the next step. (If $R_{1}$ loops or rejects, $R_{in t er sec t}$ will do the same, which is correct behavior since w is not in $L_{1}$ and thus not in the intersection).
Run the recognizer $R_{2}$ on w.
If $R_{2}$ halts and accepts, then $R_{in t er sec t}$ accepts and halts. (If $R_{2}$ loops or rejects, $R_{in t er sec t}$ does the same, which is correct since w is not in $L_{2}$ ).

This sequential design correctly recognizes $L_{1} \cap L_{2}$ . If w is in the intersection, both $R_{1}$ and $R_{2}$ must accept in finite time, so $R_{in t er sec t}$ will accept. If w is not in the intersection, $R_{in t er sec t}$ will correctly not accept (it may reject or loop).

Test your understanding!

Why can we use a simple sequential simulation for the intersection of two RE languages, but we need a parallel simulation for their union?

Show answer

For intersection, a string w must be accepted by both recognizers. If the first recognizer R1 loops, it means w is not in L1, and therefore not in L1 ∩ L2. In this case, it is correct for the combined machine to also loop. We only need to proceed to R2 if R1 definitively accepts.

For union, a string w only needs to be accepted by one of the recognizers. If we run R1 first and it loops on a string w that is actually in L2, we would never get the chance to run R2 and find the correct "accept" answer. Parallel simulation ensures both machines get a chance to run.

The following video segment confirms our proofs for intersection.

Closure Properties of Decidable and Turing recognizable languages

This segment continues the discussion on closure properties, focusing on intersection. It confirms the sequential simulation works for both decidable and Turing-recognizable languages.

Watch from 20:41 to 24:27. Note how the argument for Turing-recognizable languages allows for sequential execution, in contrast to the union case.

3. The Decisive Role of Complementation

The learning outcome focuses on union and intersection, but we cannot ignore complement. It is the property that most clearly separates recursive and RE languages.

Recursive languages are closed under complement.
The proof is simple: take the decider M for a recursive language L. Construct a new TM M' that is identical to M but with its accept and reject states swapped. Since M is guaranteed to halt on all inputs, M' is also guaranteed to halt on all inputs, and it will accept exactly the strings that M rejects. Thus, M' decides $L^{c}$ .
RE languages are NOT closed under complement.
This is a profound result that we can prove using Post's Theorem from our last lesson.
Proof by Contradiction:
1. Assume for contradiction that the class of RE languages is closed under complement.
2. We know there exists a language $L$ that is RE but not recursive (our canonical example is $A_{T M}$ ).
3. If RE languages are closed under complement, then $L^{c}$ must also be RE.
4. So now we have that both $L$ and $L^{c}$ are RE.
5. But by Post's Theorem, if a language and its complement are both RE, the language must be recursive.
6. This contradicts our initial statement that $L$ is not recursive.
7. Therefore, our assumption in step 1 must be false. The class of RE languages is not closed under complement.

This result highlights the asymmetry of RE languages: they can confirm membership, but they can't always refute it.

Summary

Let's summarize our findings on the closure properties of these two important language classes.

Operation	Recursive (Decidable)	Recursively Enumerable (Turing-Recognizable)
Union	Yes (Closed)	Yes (Closed)
Intersection	Yes (Closed)	Yes (Closed)
Complement	Yes (Closed)	No (Not Closed)

Conclusion

In this lesson, we used constructive proofs to show that both recursive and recursively enumerable languages are closed under union and intersection. We saw how the guaranteed halting property of deciders simplifies these constructions, while the potential for looping in recognizers necessitates a more careful, parallel simulation for the union operation.

Key Takeaways:

Recursive languages are closed under union, intersection, and complement. The constructions are straightforward because deciders always halt.
RE languages are closed under union and intersection. The proof for union requires a parallel simulation to handle potential non-halting computations.
The fact that RE languages are not closed under complement is a fundamental result that distinguishes them from recursive languages and reinforces Post's Theorem.

Preview of the Next Lesson:
We have now defined the most powerful languages recognized by machines—the recursively enumerable languages. The Chomsky Hierarchy, however, is defined by grammars. In the next lesson, we will bridge this gap by defining unrestricted grammars and proving their equivalence to Turing Machines. This will complete our picture of the hierarchy, linking each class of machine to a corresponding class of grammar.

Recommended resources