An oracle is a black box that is capable of reporting, instantaneously (or, if you prefer, in 1 computation step), whether a string w is a member of a language L.

An oracle TM is a Turing machine, but with the extra capability of querying an oracle to determine a string's membership in a language. We sometimes use the convention M^L to name an oracle TM that has an oracle for language L.

How does M^L work? Suppose it has an "oracle tape" in addition to its usual tape or tapes. When M^L wants to ask the oracle a question, it writes the string that it's interested in querying the oracle about on the oracle tape, and then it goes to state q, its query state. State q says, "Hey, oracle? Tell me if the string on the oracle tape is a member of language L." The oracle then magically erases the contents of the oracle tape and leaves a single bit there, 0 or 1, telling the machine whether or not the string was or was not a member of L. All this happens in one computation step.

The rest of the TM isn't concerned with, and can't know, how the oracle does what it does. Similarly, the oracle isn't concerned with and can't know what the rest of the TM does. For example, the oracle does not know what the TM receives as input. All it knows is what the TM decides to write on the oracle tape prior to entering state q. The oracle tape is the only interface between the oracle and the rest of the TM.

Obviously, an oracle TM can be very powerful. For instance, it can solve the acceptance problem, which is: given input <M, w>, which is an encoding of a TM M and a string w, does M accept on input w? To solve this using an oracle, "all" you need is an oracle for the language of all strings <M, w> such that M accepts on input w. So you just stop by the oracle store and pick one of those up, and then you can build your TM to solve the acceptance problem, which is so simple that it barely needs explaining: on input <M, w>, copy the input directly onto the oracle tape, go to the query state, and wait for the answer. If the oracle returns a 1, for "yes, that's in the language that I'm an oracle for", we accept, and if the oracle returns a 0, for "no, that's not in the language that I'm an oracle for", we reject.

So, obviously, we can decide an undecidable language as long as we have an oracle for that particular language. As it turns out, deciding the complement of the language decided by an oracle TM is also very easy. For instance, given our oracle TM that uses our oracle for the acceptance problem, we can also decide the complement of the acceptance problem, that is, the language of all strings that are not encodings of a TM M and a string w such that M accepts on input w. We just swap the accept and reject states. If the oracle says that the string on the oracle tape is in the language, we reject. If the oracle says that the string is not in the language, we accept. This is a powerful notion, because the complement of the acceptance problem is Turing-unrecognizable. So, with our magical oracle TM, we can decide a language that isn't even Turing-recognizable. (Recall that if a language is Turing-recognizable, then it's the set of all strings that some TM accepts. This is also called "semi-decidable" because it's half of what's needed for decidability.)

So, obviously, we can decide an undecidable language as long as we have an oracle for that particular language, and we can even decide a Turing-unrecognizable language if it's the complement of the language decided by an oracle TM. More interestingly, we can potentially solve other problems with that same oracle. For example, using the oracle for the acceptance problem, we can solve the emptiness problem, which is: given input <M>, which is an encoding of a TM M, does M accept nothing? In other words, we want the language of all strings <M> such that M is a Turing machine that rejects on all inputs. How can we decide that language using the oracle for the acceptance problem? We build a new machine D which operates as follows: on input <M>, where M is a TM, we start by constructing a new Turing machine N, which is based on M and operates as follows. N ignores its input and runs M in parallel on all strings in the alphabet, and if M accepts on any of those strings, M accepts. Now, obviously this TM N might run forever, depending on the alphabet. But that's okay because we are never going to run N. Instead, we go to the oracle tape and write <N, foo> on the tape where foo is some sort of dummy input. It doesn't matter what foo is because N ignores its input anyway. Then we go to the query state. Recall that we have an oracle for the acceptance problem, so the oracle will tell us immediately if N accepts on input foo. If the oracle says yes, then we know that M accepts some string, which means that M does not reject on all inputs. So, D rejects. But if the oracle tells us no, then we know that M does not accept any string. So, D accepts.

The emptiness problem is undecidable, but D decides the emptiness problem with the help of its oracle for the acceptance problem. So, we say that the emptiness problem is decidable relative to the acceptance problem.

This brings us to the notion of Turing reducibility. We say that language A is Turing reducible to language B if language A is decidable relative to B. So, the emptiness problem is Turing reducible to the acceptance problem.

Now, if A is Turing reducible to B and B is decidable, then A is decidable. Why? Because if B is decidable, then we could replace the oracle that decides B with an actual procedure that decides B. (We're not concerned about running time of the procedure right now; only with decidability.) So we no longer need an oracle TM to decide A; we can just use a regular TM to decide A. Therefore, A is decidable. Another way to say this is that if A is decidable relative to another decidable language, then A is also decidable. Of course, as we know, the acceptance problem is not decidable. If it were, then the emptiness problem would be decidable since the emptiness problem is Turing reducible to the acceptance problem.

You might think that with this magical oracle for the acceptance problem, we would be able to build oracle TMs to decide all languages (relative to the acceptance problem). But, in fact, it is possible to show that languages exist that are not even recognizable by an oracle TM with an oracle for the acceptance problem.

Now, let's move away from the realm of decidability and undecidability for a minute and talk about time complexity. Relativization is useful here, too.

What would it mean to have P^P? Let's walk through it: P^P is the class of languages L such that L is accepted in polynomial time using an oracle TM with an oracle for some polynomial-time-decidable language. This idea is kind of intrinsically silly, because we don't need an oracle for a polynomial-time-decidable language, because we can do the work of deciding it on our own, thanks! So the class P^P turns out to be just plain old P. So, we don't talk about languages (or classes of languages) relativized to P very often, because it's just not interesting.

Let's talk about a more interesting example. Suppose, for instance, that we had an oracle for deciding SAT. Then, we could construct a polynomial time solver for any problem in NP. We would just have to reduce that problem to SAT, and then pass the result along to the oracle, which would immediately tell us whether the result was a member of SAT or not. So, all of the languages in NP are in P relative to SAT. We say that NP is contained by P^SAT.

We can also say something interesting about coNP. Now, coNP is a little confusing. It's easy to screw this up and think that coNP means "complement of NP", but that is not quite right (and doesn't make sense since NP is not a language, it's a class of languages). Instead, coNP is the class of complements of languages that are in NP.

Now, we know that all languages that are in NP are also in P^SAT. So, therefore, coNP is a class of complements of languages that are in P^SAT. And we know that the complement of every language that is in P^SAT is also in P^SAT (because deterministic complexity classes are closed under complementation). So, all of coNP must be in P^SAT. In fact, because SAT is NP-complete, we could stop talking about P^SAT and just think of SAT as a representative for all of NP, and from now on speak of P^NP. P^NP is either the same class as NP or it's bigger. Relativization to NP is much more interesting than relativization to P.

Now, consider for a second the class NP^NP. Reminder of what this means: it is the class of languages that are decidable in NP by an oracle TM using an oracle for a language that is in NP. As shorthand for NP^NP, we write NP₂.

And we can keep going with this shorthand. For instance, NP₃ = NP^NP₂ -- and so on upward. And all these classes of languages, all the NP_k, are called the polynomial time hierarchy.

Final thought: If NP equals P, then this entire hierarchy collapses. NP_k would equal NP for all k.