Computer Science 4602, Fall 2016
Assignment 4

Exercises are from Sipser, third edition, beginning on page 154 (for Chapter 2) and 187 (for Chapter 3). Exercise 4.20 is on page 212.

1. 2.12
2. 2.16
3. 3.6
4. 3.9(a,b)

5. 4.20.
   Hints. A language is co-Turing-recognizable if its complement is Turing-recognizable (partially computable). Suppose that A and B are disjoint co-Turing recognizable languages. So A and B are Turing-recognizable.

   1. You would do well to draw a Venn diagram of sets A, B and C.

   2. If A and B are disjoint, what can you say about set A ∪ B?

   3. If a problem is Turing-recognizable, you can assume that you have a recognizer for it. Remember that a recognizer for L stops and answers yes on all inputs that belong to L (but might not stop at all on inputs that do not belong to L).

   4. Produce the set C by writing a program that decides it. (The program serves as C's definition.) The program can run the recognizers for A and B. How can your decider be sure that it says yes on every input that is in A and says no on every input that is in B?