CSCI 6420
Spring 2004
Homework assignment 2

Due: Tuesday, February 17

These problems are from Sipser.

  1. Exercise 5.7. Pay attention to the definition of a mapping reduction here. The statement would not be true for a Turing reduction. Mapping reduction preserves not only computability, but also partial computability and co-partial computability.

  2. Exercise 5.9. For this exercise, think in terms of a Turing reduction to the halting problem. Remember that, if A is partially computable (Turing recognizable) then there is a program that halts on members of A and does not halt on nonmembers of A. You will want to use that program, and you will want to use the oracle for the halting problem. Once you have that step, you should discover that you have only used the oracle once, and that you give the same answer that the oracle does. Describe the mapping function, which just produces the question that you ask the oracle.

  3. Exercise 5.12. See Exercise 5.22.

  4. Exercise 5.13. A state is just an instruction in a program. A useless state is an instruction that is never executed, for any input string. What if you are looking at a state that is the sole halt instruction in the program? You might find it useful to reduce from a problem other than the halting problem. A suggestion is the set of programs that terminate on some input; that is, the set {p | there exists an input x on which p will halt}. How can you argue that this set is uncomputable? There is an easy argument.

  5. Exercise 5.18. Explain how to reduce PCP over an arbitrary alphabet to PCP over a binary alphabet. (How do you handle large alphabets in a computer, even though, internally, the computer only uses 0's and 1's?)

  6. Exercise 5.19. The problem gives you the reduction. You just need to argue that it works. What language is derivable from T? What language is derivable from B? What is the intersection of those two languages, and under what circumstances is that intersection nonempty? (If the intersection is nonempty, then the grammar is ambiguous, since the same string can be derived in two ways, one beginning with S => T and another beginning with S => B.) Note that a1, ..., ak are individual symbols that do not occur on the dominoes.