1
$\begingroup$

In the Reducibility chapter of Sipser's Theory of Computation book, an example is:

We reduce A(TM) to HALT(TM). And then we claim that if H decides HALT(TM), then A decides A(TM), but since A(TM) is undecidable, so is HALT(TM)

My question is, if we already know that A(TM) is undecidable, what is the need for deciding HALT(TM). It's a basic question though.

Hope you got it.

$\endgroup$
  • $\begingroup$ @Louis This particular misunderstanding of the problem statement is quite specific; I can't remember we dealt with it before. (If you see a question that you don't think deserves an answer, consider close-voting or, failing that, flagging it.) $\endgroup$ – Raphael May 5 '14 at 20:03
1
$\begingroup$

There's a difference between the statements:

  • There is an undecidable problem.

and

  • The problem HALT(TM) is undecidable.

For the first one, it sounds like you proved by by showing directly

  • The problem A(TM) is undecidable.

The point of using a reduction, is that it lets you deduce the undecidability of HALT(TM) from the undecidability of A(TM), as opposed to starting "from scratch". More generally, reductions let you compare the hardness of different problems to each other, which is a general theme in computability and complexity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.