1
$\begingroup$

If one could build a machine that for any input will never accept, but always loop forever, then will all problems reduce to this?

Or did I just misunderstood the idea of reduction?

|cite|improve this question
$\endgroup$
3
$\begingroup$

a machine that for any input will never accept, but always loop forever

isn't a decision problem, and so it doesn't make sense to say it's undecidable.

However, given an undecidable problem $A$, there are always "more undecidable" problems $B$, i.e. those which would be undecidable even given an oracle for $A$. For example, the halting problem for Turing machines extended with an oracle for $A$.

|cite|improve this answer
$\endgroup$
-4
$\begingroup$

The idea of reduction for a decision problem, is to prove that a NP-Complete problem is at least solvable in terms of another NP problem. As in, we break down (reduce) a problem to show that it may be solved.

Not all problems can be reduced to to be undecidable, only those that are not solvable in polynomial time such as NP-Hard problems.

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ Welcome to Computer Science Stack Exchange. Unfortunately, this answer is almost completely wrong. Reductions are not tied to the concept of NP-completeness, and it makes sense to talk about reductions between almost any pair of problems, regardless of what complexity classes they're in. "Reduction" does not mean "breaking down"; rather, it means translation between problems. If you like, it "reduces" the amount of work you need to do, since you show how to solve one problem by translating it into one that you maybe already know how to solve. $\endgroup$ – David Richerby Nov 29 '14 at 19:37

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.