CSCI 4602
Fall 2000
Homework assignment 9.

Due: Friday 10/13

  1. Exercise 5.4 of Sipser. If A mapping-reduces to B and B is a regular language, does that imply that A is a regular language? Why or why not?

  2. Two programs are equivalent if they give the same answer on every input. In cases where one goes into an infinite loop, the other must also go into an infinite loop.

    Prove that the language A = {(p,q) | p and q are equivalent programs} is uncomputable.

    Hint. The language B = {p | p loops forever on every input} is uncomputable. Do a reduction to show that A is uncomputable.

  3. Show that the language Z = {p | p halts on input 0} is uncomputable.

    Hint. Do a reduction from the halting proglem. You will want to design a program that ignores its input, so that it will do the same thing on every input.