11
$\begingroup$

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 :)

$\endgroup$
3
  • 16
    $\begingroup$ If O can solve the halting problem for M, then M is a "normal" machine which doesn't have access to O. $\endgroup$ Jul 23, 2010 at 5:35
  • $\begingroup$ Ah, thank you. That's the elementary error I was looking for. $\endgroup$ Jul 23, 2010 at 5:36
  • $\begingroup$ have always felt there might be some possible logical contradictions that can ensue from "not careful use" ala contradictions that were found in the foundations of calculus long ago. $\endgroup$
    – vzn
    Mar 6, 2013 at 18:03

6 Answers 6

17
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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 Ek (k is the key), an encrypted message Ek(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 :)

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Consider how Turing defined oracles (he being the one who created the notion--this quote is from his paper "Systems of Logic Based on Ordinals" found on pp. 156-7, and pg 154 of Jack Copeland's book, $The$ $Essential$ $Turing$):

"Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go into the nature of this oracle apart from saying it cannot be a machine. With the help of this oracle we could form a new kind of machine (call them $o$-machines), having as one of its fundamental processes that of solving a given number-theoretic problem. The moves of the machine are are determned as usual by a table except in the case of moves from a certain internal configuration $\mathfrak o$. If the machine is in the internal configuration $\mathfrak o$ and the sequence of symbols marked with $\mathfrak l$ is then the well-formed formula $A$, the machine goes into the internal configuration $\mathfrak p$ or $\mathfrak t$ according as it is or is not true that $A$ is dual." ['$A$ is dual' means that $A$ satisfies the following property "Every number-theoretic theorem is equivalent to a statement of the form '$A(n)$ convertible to 2 for for every W.F.F. $n$ representing a positive integer' (in Church's $\lambda$-calculus), $A$ being the W.F.F. determined by the theorem"....this simply means that for Turing's purposes, his oracle is interested in determining whether or not $A$ is a number-theoretic theorem--of course this notion can be generalized as follows: given a Goedel number $n$ in the internal configuration $\mathfrak o$, the $\mathfrak o$-machine will go into the internal configuration $\mathfrak p$ or $\mathfrak t$ according as it is or is not true that $n$$\in$$S$, the nature of $S$ to be determined.]

It is this concept that the OP believes to be essentially unsound.

After the OP's elementary error is is discovered and is realized and accepted by the OP, one can still ask the question "Is it still essentially unsound?" The reason one might still say that the notion of oracle is unsound is because the means by which the oracle determines whether '$n$$\in$$S$' or not is not, or cannot be, specified.

I argue that they can, though not in terms (of course) of Turing machines. One should first note that Turing describes an oracle as a "fundamental process" that "cannot be a machine" (i.e. not reducible to a Turing machine). What does this mean? Well, it means (at least to me) that an oracle cannot be defined in terms of a set of quadruples of the form $<$$($$i$$)$ $internal$ $configuration$,$($$ii$$)$ $cell$ $condition$, $($$iii$$)$ $operation$, $($$iv$$)$ $internal$ $configuration$$>$ satisfying the the usual internal configurations or operations that define a Turing machine that satisfy the consistency condition (the consistency condition is the restriction that any two distinct quadruples must differ at $($$i$$)$ or $($$ii$$)$ but note that the consistency condition must be satisfied by any machine). What does this mean for the internal configuration $\mathfrak o$? That $\mathfrak o$ must be a internal condition (state) of higher 'type' than the ordinary Turing machine states that correspond to the operations of '$1$', '$B$', '$R$', '$L$' ('$1$' prints a 1 on a cell of the tape if the cell is blank, otherwise no change is made on the tape; '$B$' erases the cell if there is a 1 on the cell, otherwise no change is made on the tape; '$R$' moves the device one cell to the right, '$L$' moves the device one cell to the left--note that by the consistency condition, each internal condition and input is uniquely associated with an operation).

As an example, consider the device with internal configurations $q_0$ and $q_1$ whose behavior is determined by $q_0$$1$$B$$q_1$ and $q_1$$B$$R$$q_0$ (this example is found and is quoted almost verabtim by me, from pg 14 of Hartley Rogers $Theory$ $of$ $Recursive$ $Functions$ $and$ $Effective$ $Computability$). (I continue the quote) If such a device is given a tape with a finite run of consecutive 1's and is started in state (internal configuration) $q_0$ on the leftmost cell of the run, it will erase all of the 1's and then stop. If such a device is started on a tape consisting entirely of 1's (i.e. an infinitely long string of 1's on an infinitely long tape), it will never stop. The question now is, can a Turing machine decide whether this simple Turing machine Rogers describes halts or not? A Turing machine should be able to determine, for a finite sequence of 1's that it halts, but how does one code the case where there is an infinite sequence of 1's (I won't consider the case where the tape is completely blank or where there are blank cells before the cells containing 1's since Rogers didn't provide a complete enough description to determine the behavior of the device on those and other inputs)?

So let's consider only the two inputs Rogers considers--the finite sequence of 1's or the infinite sequence of 1's and consider each case: i) the case where it is possible to provide a code for the infinite sequence of 1's and ii) where it is not possible to provide such a code. For case i) even though a Turing machine could (hypothetically) decide whether {$q_0$$1$$B$$q_1$, $q_1$$B$$R$$q_0$} halts or not, one could easily devise a higher-order instruction which would decide, given that the input was an infinite string of 1's, that the device wouldn't halt. For case ii) it is clear that a higher-order instruction would be needed. Indeed, for the halting problem, the machine that would decide whether a Turing machine would halt or not for all inputs would need higher-order instructions for some inputs in order to avoid the self-reference that produces the contradiction which makes the machine (that decides whether a Turing machine for all inputs halts or not), not a Turing machine. Such steps would, for course, be fundamental processes and would qualify for the title, 'oracle'.

This is not a new concept. Goedel, in footnote 48a or his paper " On Formally Undecidable Propositions of Principia Mathematica and Related Systems I" (found in Martin Davis' book $The$ $Undecidable$), says:

"The true reason for the incompleteness which attaches to all formal systems lies, as will be shown in Part II of this paper, in the fact that the formation of higher and higher types can be continued into the transfinite (cf. D, Hilbert, "Uber das Unendliche", Math. Ann. 95, p. 184), while, in every formal system, only countably many are available. Namely, one can show that the undecidable sentences which have been constructed here always become decidible through the adjunction of sufficiently high types (e.g. of the type $\omega$ to the system $P$)."

Also, this:

"It should be expressly noted Theorem XI (and the corresponding results about $M$ and $A$) in no way contradicts Hilbert's formalistic standpoint. For the latter presupposes only the existence of a consistency proof carried out by finitary means, and it is conceivable that there might be finitary proofs which cannot be represented in $P$ (or in $M$ or $A$)." [On pg. 37 of $The$ $Undecidable$]

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I forgot to mention that oracles need to be a decidable language. And to answer your question consider a P machine M (machine with polynomially-bounded resources) with an oracle to another P machine N. Then $L(M^N) \in P$, and in general $P^O=P$ for any given $O$. So here there is no contradiction. $\endgroup$ Jul 23, 2010 at 8:17
  • $\begingroup$ If I understand correctly, there is no problem with using undecidable languages like the halting problem H as oracles. Using an H oracle introduces a new halting problem, i.e., a halting problem for TMs using an H oracle. This eventually leads to the notion of the arithmetical hierarchy. $\endgroup$
    – MRA
    Jul 23, 2010 at 8:45
  • $\begingroup$ Yes, but to my knowledge in complexity only decidable languages are used as oracles. $\endgroup$ Jul 23, 2010 at 8:49
  • $\begingroup$ Yes, but this is simply because complexity theory is only concerned with solvable problems. For all practical purposes it is not relevant whether a certain unsolvable (undecidable) problem is, say, logspace reducible to the halting problem. $\endgroup$ Jul 23, 2010 at 13:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.