7
$\begingroup$

I'm learning about Turing reductions at the moment and I'm just wondering is there any difference between an oracle and a decider, As they seemingly do the exact same thing. I understand the point of a oracle is that we don't have to know how it gets its answer but it will always give us the right answer.

An oracle for a language B is an external device that is capable of reporting whether any string w is a member of B

which is the exact same thing as what a decider does. Is there any sort of difference between the two?

$\endgroup$

1 Answer 1

4
$\begingroup$

Oracles are entities capable of deciding even undecidable problems. Deciders, on the other hand, are essentially Turing machines (without an oracle) and therefore cannot solve undecidable problems (e.g. Halting problem).


I understand the point of a oracle is that we don't have to know how it gets its answer but it will always give us the right answer.

This is in fact the key difference.

An oracle doesn’t have an implementation, it is just a black box giving answer to any particular question (most importantly, the ones we cannot answer), whereas a decider has to be well defined Turing machine. In other words, we must know how a decider gets the answer, meaning it cannot answer any question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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