10
$\begingroup$

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?

Improve this question
$\endgroup$
12
  • 3
    $\begingroup$ "It's not real, so why talk about it?" That idea might make your dealings with mathematics rather rough. Which is what this is. Computer science is a branch of mathematics and much of it is of purely theoretical interest. $\endgroup$
    – Karolis Juodelė
    Commented Mar 20, 2015 at 20:57
  • $\begingroup$ @KarolisJuodelė So you mean they had no purpose ? $\endgroup$
    – M a m a D
    Commented Mar 20, 2015 at 21:06
  • 1
    $\begingroup$ There are other oracles besides the one for the halting problem. In fact, there's an oracle for every problem. $\endgroup$
    – Raphael
    Commented Mar 20, 2015 at 22:16
  • 3
    $\begingroup$ Oracles are usually used to show relations among certain classes of undecidable problems (like $A_{TM}$ and $E_{TM}$ - they are both undecidable, but how do they relate to each other?). However, they are also used for decidable classes, like $\mathcal{P}$, $\mathcal{NP}$, and so on in the same way - this is called "relativization." $\endgroup$
    – Ryan Dougherty
    Commented Mar 20, 2015 at 22:26
  • 1
    $\begingroup$ Yes, in a sense. You may see in the literature (Sipser's book, for example) a relation $A \le_T B$ ($A$ is "Turing-reducible" to $B$), which means that: given an oracle for $B$, I can decide/recognize (depending on the question) $A$. It is an easy exercise to show that there is an infinite "hierarchy" of languages equipped with oracles (i.e., each level is not Turing reducible to another). $\endgroup$
    – Ryan Dougherty
    Commented Mar 20, 2015 at 22:31

2 Answers 2

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

Some optimization algorithms are formulated as algorithms for an oracle Turing machine. This is common, among else, in submodular optimization. An algorithm for minimizing or maximizing a submodular function given some constraints typically has oracle access to the submodular function (and sometimes to the list of constraints). This has the advantage of making it possible to prove tight lower bounds. For example, consider the problem of maximizing a non-negative submodular function. There is a polynomial time algorithms achieving a $1/2$ approximation, but any algorithm doing better (in the worst case) has to access its oracle exponentially many times.

Improve this answer
$\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.