# Why is Oracle Turing Machine important?

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?

• "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. – Karolis Juodelė Mar 20 '15 at 20:57
• @KarolisJuodelė So you mean they had no purpose ? – M a m a D Mar 20 '15 at 21:06
• There are other oracles besides the one for the halting problem. In fact, there's an oracle for every problem. – Raphael Mar 20 '15 at 22:16
• 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." – Ryan Mar 20 '15 at 22:26
• 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). – Ryan Mar 20 '15 at 22:31

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