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?
$\begingroup$
$\endgroup$
asked Nov 29 '14 at 18:55
Add a comment
|
$\begingroup$
$\endgroup$
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$.
$\begingroup$
$\endgroup$
1
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.
-
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
