Let M1 be a TM that semi-decides L1 and let M2 be a TM that semi-decides L2. The following TM M semi-decides L = L1 union L2: Let M = "on input string w:(Equivalently: non-deterministically, choose M1 or M2, and run the selected machine over w. If that machine accepts w, then accept.) "
- Run M1 and M2 in parallel.
- If either one accepts w, then accept.
- If both M1 and M2 reject w, then reject.
We show that M semi-decides L = L1 union L2: M accepts w iff either M1 or M2 or both accept w iff w belongs to L1 or to L2 or to both iff w belongs to L1 union L2. Note that the machine M may loop on input w if both M1 and M2 loop on w, or if one of these machines loops on w and the other one rejects w. However, if w belongs to L1 union L2, then M is guaranteed to halt accepting input w.
Solution: See proof of Theorem 5.2 on pages 173-174 of the textbook.
(Note that your answer to this question in the quiz should contain a full proof of the fact that E_{TM} is undecidable. You cannot just cite that this is a theorem in the textbook.)