Oracles

An oracle in computer science is a purely theoretical device, a "magical black box", which can perform some computation, usually known to be impossible or difficult with computers. It is "purely theoretical" because they are generally only used in proofs and analyses, in order to make the proof simpler or analysis easier.

Oracles find their way into computability/decidability analysis, complexity analysis, cryptography, and artificial intelligence.

In computability/decidability analysis, oracles are typically called upon to perform a computation known to be impossible. For example, suppose one had a magical black box, an oracle, that could solve the halting problem. (Elementary computer science shows that the halting problem is impossible to solve with any kind of normal computer, no matter how fast or big it is.) But suppose one did. The argument goes "then what?" It turns out among the many problems that a normal computer cannot solve, some of these problems can be solved with access to the oracle, whereas others still cannot be solved even with this oracle. This pure thought experiment involving an unrealizable object partitions the space of impossible problems into two distinct sets, which we may perhaps label "Easier than the Halting Problem" and "Harder than the Halting Problem". Thus, there is a hidden structure among abstract computability problems that is revealed by an argument involving an oracle. Some people find this interesting.

Assuming an oracle surprisingly does not break the world. That is, although the argument or proof begins with a statement known to be false, it still achieves a useful result. On the other hand, if we began the proof with a different statement known to be false, "False equals True", the world breaks. Nothing interesting can be derived from such a statement.

As an aside: Does this Turing Machine accept all strings? Is the language of this Turing Machine empty? These problems may be harder than halting (one can check). Is one harder than the other?

An oracle in computability/decidability analysis most resembles the popular conception of an oracle: someone who has a special connection to God and can know things that no normal human can possibly know. But human history is fraught with struggles over who is or was really an oracle, but in computer science, an oracle is always purely theoretical: it does not really exist, we don't expect it to exist, and we aren't trying to make one. It is just a method for analyzing and exploring computer science theory.

Complexity theory in computer science deals with how long (how much computation) it will take for a computer to solve a problem. (Sometimes it deals with how much memory it will take, as well.) Oracles in complexity theory are often called upon to perform not-impossible computation, but perform it at impossible speed, often constant time. For example, sorting by comparison has been proven to take at least O(n log n) time (actually not big-O but big-Theta to be precise). However, suppose we had an oracle that could sort in constant time, no matter the number of items to sort: highly unrealistic, of course. "Then what?" so the argument goes. It turns out you can sometimes prove that, even with some oracle, a computation will take some amount of time, thus one can conclude that here in real world, where no impossibly-fast oracle exists, the computation must take at least that amount of time. Such a result is often useful, in a depressing way: give up now.

I have often read that there exist oracles that make P=NP (obviously one that can solve 3SAT in polynomial time will do it), and there exist oracles if they were to exist, make P not equal to NP. The latter case confuses me. Cannot one simply choose not to use the oracle and achieve the same answer that P!=NP?

In cryptography, one most often hears of a "random oracle". This oracle is simply a perfect cryptographic hash function. It is usually expected to run in constant or linear time in the length of the input. A hash function takes input, a "message", of arbitrary length and returns a hash, or a "digest", typically a fixed-size bit-string. A good cryptographic hash function has the properties that it is very difficult to produce two different messages that have the same hash, and given a hash, it is difficult to produce a message that has that hash. It also ought to have other desirable properties, as captured by the idealized random oracle.

One can imagine a random oracle as an entity with infinite memory living inside a black box which does the following. Upon receiving a message, it first checks its memory to see if it has seen this message before. If it has, it returns, i.e., outputs, the same hash as it did last time. If not, it flips a coin the appropriate number of time for the width of the hash, and outputs that hash, and then remembers it for the future if it ever sees the message again.

I wrote up above that in decideability analysis, one isn't trying to construct an oracle, but in cryptography, people are trying to construct random oracles, i.e, hash functions. Whereas it's known that you will never have a hash function that will perform as well as the God-in-a-box described above, functions (algorithms) such as SHA-512 in the SHA-2 family and Whirlpool are thought to approximate it fairly well, and are quickly computable, and most importantly do not require infinite memory, in fact, they require no persistent memory at all between successive calls. (I say "are thought" as some people think hash functions still have a long way to get better.)

In artificial intelligence, surprisingly the oracle exists. Artificial intelligence deals with trying to get a computer to solve a problem that humans can do easily, for example handwriting recognition. An oracle is therefore just a normal human who can do the task that the computer is trying and perhaps failing to do. Computers have a hard time with reading hand-written text and generally do poorer than humans. Oracles are not so often used in arguments in artificial intelligence. However, an proof or an analysis might go something like this. Our algorithm for handwriting recognition has such-and-such accuracy. However, if it given access to an oracle who will give the right answer to just such-and-such small number of the cases, the algorithm's accuracy increases dramatically.

The "oracle" in question is a human being who can read the handwriting, or even ultimately the person who originally wrote it, so knows what it actually says. However, the word "oracle" still has the same usage as in other fields of computer science: the oracle is an external entity (outside the algorithm or computer) which is consulted to give the right answer to a problem.

It is flattering to think that in artificial intelligence, just we regular humans are oracles. In a computer's eyes, we are gods and messiahs. Or perhaps artificial intelligence researchers like to think of themselves as such for their computers.