Cheap and Secure Web Hosting Provider : See Now

Can all decision problems reduce to undecidable?

, , No Comments
Problem Detail: 

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?

Asked By : revisingcomplexity
Answered By : Alexey Romanov

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33627

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback