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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityIf 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?
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$.
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.