Final answer:
To prove that recursively enumerable languages are closed under union, consider two such languages with their respective Turing Machines. A new Turing Machine can recognize the union by simulating both machines either in sequence or through interleaved computation steps and accepting if either original machine accepts.
Step-by-step explanation:
To show that the family of recursively enumerable languages is closed under union, we need to consider two recursively enumerable languages, L1 and L2, and their corresponding Turing Machines, M1 and M2, which recognize them.
We want to construct a new Turing Machine, M, which recognizes the language L = L1 ∪ L2. The simplest way to do this is to design M to simulate both M1 and M2 in parallel on separate tapes or in sequence and accept if either M1 or M2 accepts.
For each input string w, M runs M1 on w and M2 on w. If either machine enters its accepting state, M accepts w, thus accepting all strings in L1 or L2, or both. This proves that the union of two recursively enumerable languages is also recursively enumerable.
However, practically, M cannot simulate both Turing Machines truly in parallel; instead, it can interleave their computation steps. M can alternate between simulating a step of M1 and a step of M2.
If either M1 or M2 enters an accept state while being simulated, M accepts the input string. This interleaving method ensures that if w is in L1 or L2, then w will eventually be accepted by M.