### 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:
Run M1 and M2 in parallel.
If either one accepts w, then accept.
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.)
```