CS4123 Theory of Computation. B-2002
Quiz 2 - November 26, 2002


Prof. Carolina Ruiz.
Department of Computer Science.
Worcester Polytechnic Institute

Solutions by Carolina Ruiz

Problem I. Semi-Decidable languages (10 points)

Let Sigma be an alphabet. Show that the set of semi-decidable languages over Sigma is closed under union. That is, show that if L1 and L2 are semi-decidable languages,
then L1 union L2 = {w in Sigma* | w belongs to L1 or to L2 or to both} is a semi-decidable language.
  1. (6 points) Assuming that L1 and L2 are semi-decidable, construct a Turing machine that semi-decides the union of L1 and L2. (Pseudo-code is enough.)
    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:
    
    1. Run M1 and M2 in parallel.
    2. If either one accepts w, then accept.
    3. If both M1 and M2 reject w, then reject.
    (Equivalently: non-deterministically, choose M1 or M2, and run the selected machine over w. If that machine accepts w, then accept.) "
  2. (4 points) Prove that your Turing machine above semi-decides the language L1 union L2.
    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.
    

Problem II. Undecidable languages (10 points)

Prove that the following language ETM is undecidable:

ETM = { < M > | M is a Turing machine and L(M) = the empty set}.
That is, prove that the problem of determining whether or not a given Turing machine M accepts no words is undecidable.

Hint:

By way of contradiction assume that ETM is decidable and use a decider for ETM as a subroutine of a decider for the undecidable language
ATM = { <M,w> | M is a TM and M accepts the word 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 ETM is undecidable. You cannot just cite that this is a theorem in the textbook.)