Reductions

[Home] [CS381 Assignments] [Exam Schedule] [Notices]


Theorem. For given x, y and z, the problem
x + y = z
is undecidable.

Proof.  For any given x, y and z, we can easily construct a Turing machine M that halts on input w if and only if x+y=z. Since for a given machine M and input x it is undecidable whether M halts on x, it is undecidable whether x+y=z.

What went wrong? Hopefully nobody expects that x+y=z is an undecidable problem. The trick is that our reduction goes the wrong way. It says: "Suppose we are able to solve the halting problem. Then we can decide whether x+y=z." It says nothing about what happens if we cannot solve the halting problem.

A correct reduction should say: "Suppose we are able to decide whether x+y=z for any x, x and z. Then for any TM M and string w we can decide whether M accepts x." with "x+y=z" replaced by some wish-to-prove-undecidable problem. Of course, we would be able to prove a statement like this only if the candidate problem is in fact undecidable.

Please bear this example in mind when... you know.