As you know, an Oracle Turing Machine (OTM) is a "black box" which somehow can tell us whether a given Turing machine with a given input eventually halts. By Church's Thesis it is impossible to design an algorithm which is able to solve such a problem.
If we will never get such a black box then why is it important and, in computer science, do they talk about it?
Asked By : Drupalist
Answered By : D.W.
Why are oracles used in the context you mentioned (where we have an oracle for the halting problem)? Because that allows us to answer questions that are fascinating, questions like "Are there problems that are even harder than the halting problem?". I'm not saying these questions are necessarily useful or important in practice -- but they are fascinating, fun, and lead to a deep theory. Just as not all art has to be directly useful, not all theory has to be directly useful.
Why are oracle Turing machines important, more broadly? They are used widely in computer science theory, to help us study the relative difficulty between different problems. They help us encode the notion of Turing reductions. They help identify some barriers to proving results in complexity theory, like proving that $P \ne NP$ (see e.g. relativizing proofs). They are useful in other places as well.
See also Are there any existing problems that wouldn't be solvable with a halting oracle?, Are all undecidable/uncomputable problems reducible to the Halting problem?, and Reductions among Undecidable Problems.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/40605
0 comments:
Post a Comment
Let us know your responses and feedback