Whats the difference between an oracle and a decider in Computational Theory?
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?
turing-machines
asked 3 hours ago
ItsYourBoi
261
New contributor
ItsYourBoi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
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?
turing-machines
asked 3 hours ago
ItsYourBoi
261
New contributor
ItsYourBoi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
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?
turing-machines
asked 3 hours ago
ItsYourBoi
261
New contributor
ItsYourBoi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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?
turing-machines
turing-machines
asked 3 hours ago
ItsYourBoi
261
New contributor
ItsYourBoi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
ItsYourBoi
261
New contributor
ItsYourBoi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
ItsYourBoi
261
New contributor
ItsYourBoi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
ItsYourBoi
261
asked 3 hours ago
ItsYourBoi
261
261
New contributor
ItsYourBoi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
ItsYourBoi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
ItsYourBoi is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
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.
answered 2 hours ago
Sandro Lovnički
8661115
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
ItsYourBoi is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102085%2fwhats-the-difference-between-an-oracle-and-a-decider-in-computational-theory%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
answered 2 hours ago
Sandro Lovnički
8661115
add a comment |
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.
answered 2 hours ago
Sandro Lovnički
8661115
add a comment |
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.
answered 2 hours ago
Sandro Lovnički
8661115
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.
answered 2 hours ago
Sandro Lovnički
8661115
edited 1 hour ago
answered 2 hours ago
Sandro Lovnički
8661115
answered 2 hours ago
Sandro Lovnički
8661115
answered 2 hours ago
Sandro Lovnički
8661115
8661115
add a comment |
add a comment |
ItsYourBoi is a new contributor. Be nice, and check out our Code of Conduct.
ItsYourBoi is a new contributor. Be nice, and check out our Code of Conduct.
ItsYourBoi is a new contributor. Be nice, and check out our Code of Conduct.
ItsYourBoi is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102085%2fwhats-the-difference-between-an-oracle-and-a-decider-in-computational-theory%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
