Exercise 1:

(a) One technique to show that a decision problem is undecidable is to reduce a known undecidable problem, like the Halting Problem, to the problem of concern. Explain what requirement on that reduction (besides being a reduction, of course) is fundamental for this approach to work. Also, state which Theorem in Sudkamp's book makes use of this requirement.

(b) Prove that the problem of deciding whether a Turing Machine M and a DFA D are such that L(M) = L(D) is undecidable.

(c) Consider the following two decision problems:

P1: Given a Turing machine T and a string w, are there more than one way (i.e., more than one execution) the machine T can accept w

P2: Given a Turing machine T and a string w, does T accept w?

Use the fact that problem P2, has already been shown undecidable , to prove that problem P1, is also undecidable.