Question

From Wikipedia (bold emphasis at the end is mine):

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.

Isn't assuming the existence of a machine which can decide the halting problem... problematic? The way I've heard it explained is that it's only problematic if you assume it can solve its own halting problem or any of the "super-oracles" above it. However, if an oracle O can solve the halting problem for machine M, can't M just use O to solve its own halting problem? Isn't that a contradiction, from which all propositions follow?

I'm sure I'm making an elementary mistake, so please point it out :)

Answer 1

Oracle machines are not "problematic". Let us consider oracle machines that have the halting problem as their oracle. Now, by "the halting problem" we mean the collection of all Turing machines (without oracle) that halt when started with an empty tape.

This can be decided by an oracle machine with the halting problem as its oracle. However, such oracle machines with halting problem oracle cannot solve the halting problem for Turing machines with the ordinary halting problem as their oracle. I.e., there is no oracle machine using the usual halting problem as an oracle that decides the set of all oracle machines with the halting problem as their oracle that halt on the empty input.

In recursion theory, there is the jump operator or Turing jump that assigns to every problem $P$ (set of words, set of natural numbers, whatever you prefer), the set of all (codes of) oracle Turing machines with the oracle $P$ that halt on the empty tape. The Turing jump of a problem $P$ is strictly more complicated (more "uncomputable") than $P$ itself, i.e., no machine with oracle $P$ decides the jump of $P$.

Answer 2

I'm not sure about complexity, but they're used all the time in security. You make the oracle able to compute whatever it is you want it to compute in one operation, then show that even if such an oracle existed, your system would still be secure.

For example, if I give you an encryption E_k (k is the key), an encrypted message E_k(M) and an oracle who can decrypt any message encrypted with k except for M, then, for an ideal encryption, you should be no better off at figuring out what M is than if I hadn't even given you an oracle!

So basically we get around the problems you mentioned by ignoring them :)

Answer 3

Before answering your question, a couple things should be made a little more precise: Roughly speaking, an oracle machine M is one that given an input number n and an oracle (subset of $\mathbb{N}$) X, outputs another natural number $M^X(n)$ (or else fails to halt). The algorithm for computing the output can't depend on the input number n or oracle X - the actual computation that gets done by the machine might of course change if the inputs are changed, but the algorithm dictating the steps of the computation is fixed. Also, the machine/algorithm must be finitistic - at any finite point in time, the machine can only have accessed finitely many bits of the oracle. Once consequence of this is that if M halts on input n with oracle X, and does so after accessing only, say, the 10 first bits of X, then M must halt on input n for any other oracle X' with the same first 10 bits as X, and produce the same output as it did before.

Now, when you say "if an oracle O can solve the halting problem for machine M," that should be interpreted as saying that there is a machine M' such that, given an input number n and finite string $\sigma$, $M'^O(n,\sigma )$ outputs HALT if $M^X(n)$ halts for any oracle X with initial segment $\sigma$, and does so using at most the first length($\sigma$) bits of X; and outputs FAIL otherwise. More simply put, saying that O solves the halting problem for M says there's some machine M' which, upon using O as an oracle, solves the halting problem for M. It doesn't say that you can use the same machine M with O to solve the halting problem for M.

But you generally don't solve the halting problem for a machine, you solve it for an oracle. The halting problem for a set X asks: "Is there an algorithm such that given any machine M and number n, the algorithm decides whether M halts on input n using oracle X?" Since machines are finitistic objects, it makes sense to talk about an algorithm which takes M and n as inputs. It also makes sense to encode M as a finite number [M], and then define X' (read "X jump" or "the halting problem relativized to X") as {(n,[M]) | $M^X(n)$ halts}. Then you say Y computes X' iff there is a machine M such that $M^Y(n,[M'])$ outputs HALT if (n,[M']) is in X', and FAIL otherwise.

You can prove X does not compute X'.

Answer 4

Oracles are used in complexity theory for lower and upper bounds in the decision tree model. Using oracles you can tell if the proof for certain problems (like P vs NP) relativizes or not. If it relativizes then you cannot use a proof based solely on diagonalization (like the halting problem) to solve it. Can also tell you about bad approaches to the problem. A good book to read about this is chapter 3 of Computational Complexity: A Modern Approach (here is the draft). A beautiful paper about oracles in complexity theory was written by Fortnow.

Some people like oracles and some don't. I particularly like them, because lower bounds are very hard to proof in a general Turing machine. Lower bounds in at least a restricted model is a step towards a real lower bound. I believe the best lower bounds we truly understand are AC0 circuits.

Answer 5

When using oracle tapes it is easier to build hierarchies of complexity. You can, by using, e.g. some $\Sigma_1$ set as an oracle tape enumerate $\Sigma_2$ sets. Or in other words, if you can enumerate some set using some $\Sigma_n$-set as an oracle tape, you have an upper bound on its complexity.

This is just one of the things one can use oracle tapes for.