Talk:Oracle machine

From Wikipedia, the free encyclopedia

Contents

[edit] Example for a particular oracle, please?

I'm having trouble visualizing an oracle machine for which PB≠NPB. Is there a succinct example? --AndStuff:ScottMoonen

Well, an extension of that question: can someone add citations to proofs of those nifty results about oracular complexity? --pde 00:55, 24 Dec 2003 (UTC)
It's equivalent to the P=NP problem. If P=NP, then PB=NPB for any oracle, and if P≠NP, then a useless oracle (such as "always outputs zero") would satisfy PB≠NPB.
Sorry, I was wrong

Yes, this is strange - if P^B \neq NP^B for some B then P \neq NP. 83.23.231.246 (talk) 15:50, 31 December 2007 (UTC)

No, that simply isn't correct. What argument do you have in mind to try to prove it? Knowing that would help me explain. The original paper by Baker, Gill, and Solovay is well written and worth reading for the details. That paper establishes that whether or not P = NP, there are oracles relative to which P = NP and oracles relative to which P does not equal NP. — Carl (CBM · talk) 05:46, 1 January 2008 (UTC)
Here is how to construct an oracle X such that PX is not equal to NPX. First, for any set M of binary strings let L(M) to be set set of binary strings y such that there is some string x in M of the same length as y. Note L(M) is in NPM, because all we need to know to prove y is in L(M) is any particular string in M of the same length as y, and the ability to test that this string is in M.
Let Pi be an enumeration of all polynomially-bounded Turing machines, and for each i let pi(n) be a polynomial that bounds the running time of Pi, as a function of the length of the input string. The goal is to construct a set X such that no Pi accepts L(X). Then L(X) will not be in PX, but it will be in NPX, so these are not equal.
The set X is built inductively; at each stage i we have a finite approximation X(i), and X is the union of the approximations. Let n(0) = 1. At stage i, we will ensure that Pi does not accept L(X). Choose n > n(i) so that pi(n) < 2n. Run machine P(i) on input 0n with oracle X(i) until it halts or runs out of time.
Case 1: If it accepts, then put nothing new into X(i+1); this will mean that 0n will be accepted by PiX but will not be in L(X).
Case 2: If it does not accept, choose some string of length n that was not queried by the machine while it ran, and add this to X(i+1); this will mean that 0n will not be accepted by PiX but will be in L(X). Note that since pi(n) < 2n, there is at least one such string. Because the string was not queried during the execution of the machine, adding it will not affect the result of the computation.
In either case, let n(i+1) = 2n and go on to the next stage. Note that no string shorter than length 2n will ever be added in the future, so the computations we observed for X(i) will be the same with oracle X.
This construction works whether or not P = NP. — Carl (CBM · talk) 06:11, 1 January 2008 (UTC)
I assume the proposed argument is simply "one can substitute equals for equals". One typically has that A=B implies A^C=B^C, otherwise the function ^ is not well-defined. The article says "The complexity class of decision problems solvable by an algorithm in class A with an oracle for a problem in class B is written A^B." and this appears to define ^ as a well-defined function. Perhaps equality among complexity classes does not actually mean equality as sets of algorithms. If not, it would not hurt to address this point. In particular, it seems reasonable to conclude from you say that even if P=NP, there is an algorithm in NP that is not in P, which is counter-intuitive to some. JackSchmidt (talk) 08:00, 1 January 2008 (UTC)
In this case, it's better to read PX as "P relative to X". Then P on its own means "P relative to the empty oracle"; we just don't write the 0 for the empty oracle in P0. It should be at least naively plausible that even if P and NP are equal relative to one oracle, they might differ relative to another oracle, and vice versa. The result of Baker, Gill, and Solovay shows that this phenomenon actually occurs. The way that you are reading ^C as a function isn't quite right; it's more accurate to think of P^(x) and NP^(x) as functions of an oracle x, so P on its own means P^(0) and NP means NP^(0).
I do agree that the article could be improved; I need to think about the best way to do it. The issue is that this entire subject is not really about oracle machines per se; it's about relativizations of P and NP. So it might make more sense to make a complete article on that subject, and just give a short summary here with a link. — Carl (CBM · talk) 15:19, 1 January 2008 (UTC)
I don't think treating P as P^(x) changes anything about the argument. If P=NP, then P^(x)=NP^(x) simply because of substitution of equals. Even if only P^(0)=NP^(0), then it is clear that (P^(0))^(x)=P^(x) and one still has that P^(x)=NP^(x).
Let me offer what I think might be a better correction (to what I would consider an error in the wikipedia article, but which might simply be a cultural and language difference). The article's definition refers to an algorithm being in P or NP. There are no algorithms in P or NP, only languages. P and NP are sets of languages which can be recognized by machines in certain classes, P_machine (polynomial time Turing machines), and NP_machine (polynomial time non-deterministic Turing machines). There is no particular need for a set of languages to be defined this way, but amongst those sets of languages defined by machines, we can define relative versions, relative to an oracle. If A is the set of languages recognized by machines in class A_m, and B is an oracle, then we can define a class of machines A_m^B containing all the machines in A_m as well as machines in A_m with one operation added, "ask the oracle B". Then we define the set of languages A^B as the set of languages recognized by a machine in A_m^B.
Why does this help? Well, it is clear from the very definition that P_m is not equal to NP_m (for every element of P_m, NP_m contains an equivalent machine, but certainly no element of NP_m is literally an element of P_m; here I am thinking of machines as tuples as per Turing machine etc.). However, there is no particular reason that two classes of machines cannot recognize the same languages. Consider the class NOOPP_m of machines which are Turing machines, running in polynomial time, which execute at least 10 "no-operations" for any input. NOOPP_m is a proper subset of P_m, but it is not hard to see they recognize exactly the same languages.
Since two distinct classes of machines can give rise to the same set of languages, it is important to make the notation reflect this. Let L(A_m) be the set of languages recognized by the class of machines A_m. Then the article definition should read more like "If A=L(A_m), then by abuse of notation, we denote L(A_m^B) as A^B when this does not cause confusion."
In other words, L(P_m)=L(NP_m) does not imply that P_m = NP_m (in fact, they are not equal), and certainly does not imply L(P_m^C)=L(NP_m^C). JackSchmidt (talk) 17:10, 1 January 2008 (UTC)
The problem with your substitution of equals argument is that even if P = NP, this doesn't mean the function P^(x) is the same as the function NP^(x); it only means that these functions have the same value when given the empty oracle. So concluding P^x = NP^x from P = NP is not a substitution of equals, and only appears to be so because of notation. This whole time I am using P and NP, and P^x and NP^x, to refer to sets of languages, not to sets of machines or sets of algorithms. — Carl (CBM · talk) 17:50, 1 January 2008 (UTC)
I agree that the "algorithm in class A' language used by the article is Bad. The way that Baker, Gill, and Solovay defined relativized complexity was by first defining polynomially-bounded Turing machines, and I don't know of a more elegant way of defining relativized complexity. But my question is still whether this should be moved to a separate article, rather than expanding this section in this article. — Carl (CBM · talk) 17:56, 1 January 2008 (UTC)

[edit] References in Popular Culture

"The Oracle character in the Matrix series is clearly a reference to oracle machines. This becomes particularly apparent in The Matrix Reloaded, with discussion of the Oracle's "intuitive" but inexplicable answers to extremely difficult problems. The Matrix Revolutions appears to explore the idea that oracle machines are unable to answer questions about their own behaviour."

Removed this from the article. Oracle machines are a pretty obscure topic that are not widely known outside of CS circles, and Delphic oracles are not - I think it far more likely that the Matrix movies were referencing the Delphic oracles, and not an esoteric CS topic... (of course, if there is any evidence from the filmmakers which supports the CS theory, re-add this.) --Kwertii 11:29, 15 May 2004 (UTC)

Well, the closest indication from the Wachowski brothers was that they said they were making films about "higher mathematics" (Google search). --pde 03:51, 2 Dec 2004 (UTC)
I agree. This is almost certainly based on oracles, the people, rather than the machines. I support its removal. --Deco 00:32, 14 May 2005 (UTC)
I don't think it's "clearly a reference" at all. It could just as easily be a reference to the Oracle at Delphi (or any other oracle- the usage of this term is relatively common throughout history), and given the authors' obvious tendenc to name characters and places from (often mystical beings) in history, (Merovingean, Morpheus, Niobe, Nebuchadnezzar, Kali, Seraph, Persephone, etc.) then this sounds sorta naïve, silly, and irrelevant. This is not a Matrix fanboy page. I'm removing. --Eliasen 14:08, 15 May 2005 (UTC)


[edit] Can anyone tell me what "single step" means?

I am confuse with the statement "which is able to decide certain decision problem in a single step". What "single step" means? Is it solving a decision problem in a constant time? In the article NP-easy, it used an example about sorting a list of strings. It seems to imply that comparing two string can be solved in "a single step". I think it is because the complexity of comparing two string is independent of(independent of n, where n is the number of strings) sorting the list of strings. Therefore, we can conclude that comparing two strings can be solve in "a single step". Am I right? Can anyone tell me what "single step" means? --wonghang

In the context of the article, "single step" means a single step of the Turing machine. Turing machines operate in discrete timesteps, and it may take the Turing machine many, many timesteps to solve a problem, but the attached oracle can solve arbitary problems in one timestep.
In the sorting case, I think they're making the assumption that each string can be compared in constant time. This can be done if the string is very short, but generally cannot be done for arbitrary length strings (because more than one machine word needs to be compared.) --Eliasen 07:26, 21 Jun 2005 (UTC)
I think perhaps it would be better to say "a single operation" rather than step. --Maru (talk) Contribs 20:51, 30 October 2005 (UTC)


[edit] Reducing to Halting problems

What is the simplest problem that can be Turing reduced to the Halting Problem? --SurrealWarrior 06:37, 1 August 2005 (UTC)

[edit] Strange observation re Turing's first proof

This Turing Oracle thing suddenly becomes apparent if you write Turing's first proof in the form of a play of people rather than a machine-- my example to myself is a married couple who are counselors of marriage-counselors (thus we have the opportunity to create self-reference). But their "counselor-method" is highly logical-- it follows a script of instructions. When an evil competitor asks them to write down their own method, and passes it off as his own, they get locked in a circle. If you imagine this to be the story of real (agreed: zombie-like) people, you as audience see this "from the outside in" whereas if you were one of the counselors, you would see a different "play" from "the inside out". You might not observe yourself being a zombie. In a way this is like a Turing machine watching a Turing machine, telling it it is in circle when it repeats a sequence of states. But I'm not convinced the "oracle" (the audience or watcher-machine in this example) can be sure it is truly watching a circle. But this example made clear what an oracle might provide a TM. Any thoughts about this? Thanks wvbaileyWvbailey 03:38, 11 January 2006 (UTC)

The more I think about this the more it bugs me (in the philosophic sense). It's clear that the "zombie-actors" could stop and ask the "audience" if the "play" is in a circle. But can they truly answer "Yes" or "No"? (Maybe this is what the article is saying re the Halting problem I dunno...). I need convincing that the "audience" can respond with truth as an oracle. I have a bad feeling that the turing circle problem is truly, utterly, completely, absolutely undecidable.

So is it possible to prove that oracles absolutely cannot exist? Do they belong in the realm of metaphysics (read: religion, the supernatural)? Take the busy beaver problem. Can we ask an oracle to answer it for a really large problem? Here's why, in the philosophic sense, we might worry:

If the universe is "grainy" down to some "Planck-length" e.g. 10^-43 cm or so, then a cubic centimeter would contain about 10^129 "grains". And the universe if it is 10 billion years old would contain approx. 10^75 cubic centimeters, or about 10^204 grains. If we were to put the entire universe "in order" the ultimate number would be about 2^(10^204), i.e. a really long string of 1's and 0's. Thus if we were able to (thank the good lord we are not) write this digits of this number the universe would be dead-frozen-absolute-zero stuck in a particular configuration. So therefore the successor number cannot exist. If a problem (busy beaver solver) is more complex (larger) than this, this universe cannot contain it. So therefore that which solves such a big problem cannot exist, e.g. an "oracle". (Example: eventually we will run out of stuff to write the digits of pi on). What am I missing here? Thanks.wvbaileyWvbailey 18:00, 12 January 2006 (UTC)

Chaitin's latest weird effort Metamath, The Quest for Omega seems to follow a similar reasoning, i.e. that, because of "noise" (randomness), at some (small) dimension numbers cease to have meaning. This would of course make the problem above even worse, because as we proceed to use up the universe, our numbers (the bit string of pi for example), would start to change (randomly).Wvbailey 19:30, 11 February 2006 (UTC)wvbailey

[edit] Nature of the oracle

I find parts of this section unnecessary. Why are there a bunch of definitions for machine? It doesn't really shed any light into what Turing meant. RyanEberhart 21:57, 20 October 2006 (UTC)

The point is: the "oracle" is not a machine of any sort whatsoever. So said Turing. That's what the man said. So what exatly is "a machine?" By accepted definition it is xyz. Therefore, the oracle is not "xyz." So just what is it? wvbaileyWvbailey
I also find this paragraph more disturbing than helpful. Turing wasn't referring to whatever commonplace meanings of "machinery", but used the term in the context of his work. The sentence "... cannot be a machine" simply indicates that an "oracle" per definitionem shall be the end of investigation, in contrast to "machines" which are subject to his analysis. Zooloo 16:15, 17 November 2006 (UTC)
I think this section should either be rewritten or removed. The quoted passage reflects the Church–Turing thesis which is not a theorem and should not be taken as indisputable. Moreover, I find the suggestion that oracles exist as "immaterial" objects rather naive and contrary to Turing's views as I understand them. - 85.75.28.21 01:57, 15 February 2007 (UTC)
I'll move the section here, since it is quite bad. In contemporary understanding, an oracle is just a set of natural numbers, and is completely different than the machine, which is essentially a regular Turing machine with an extra read-only tape. CMummert · talk 02:16, 15 February 2007 (UTC)

Turing made it quite clear that oracles are not machines:

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 any further into the nature of this oracle apart from saying that it cannot be a machine" (Undecidable p. 167, a reprint of Turing's paper Systems of Logic Based On Ordinals).
A "machine", or "a machinery" is defined as "(1) an assemblage of parts that transmit forces, motion, and energy one to another in a predetermined manner" (Webster's Ninth New Collegiate Dictionary). Likewise "a machinery" may be: "a living organism or one of its functional systems" (Webster's, ibid, etc. for more definitions). Thus a machine, or a machinery, has parts that move. An archaic definition is "a constructed thing whether material or immaterial". An oracle cannot be an assemblage of moving parts, nor can it be "a living organism or its functional systems". This would seem to render it "immaterial" and its nature to be found in metaphysics.

Since I put this in here, to make it clear what Turing wrote, I don't think it is "quite bad." It isn't "just a set of natural numbers." Turing laid out the idea in his first paper as a "choice machine" (see the first pages of 1936-1937). What it is, is a machine that offers you a choice, and you have to respond or otherwise the machine cannot go further. So it cannot be a machine, just a Turing said. wvbaileyWvbailey 16:29, 15 February 2007 (UTC)

Here is a quote from Soare (1987), the standard contemporary reference on computability; the emphasis is his.

An oracle Turing machine is simply a Turing machine with an extra "read only" tape, called the oracle tape, upon which is written the characteristic function of some set A (called the oracle), and whose symbols cannot be printed over.

Turing was brilliant to invent relative computability, but it took some time after his paper was published for everyone to realize that an oracle machine is, itself, a finite object independent of which oracle that it is run with, and that the oracle set merely determines the semantics of the computation. That is, the relation "oracle machine e running with input n and oracle set A halts and outputs m" is a just a specific four-place predicate of (e,A,n,m) where e, n, and m are natural numbers and A is a set of natural numbers. CMummert · talk 17:47, 15 February 2007 (UTC)

I don't have a problem with the notion of "the oracle" (i.e. its choice) being input from some read-only tape, or from some read-only thing or other. But somehow the symbols (oracle set) got on "the oracle tape". What is that thing that put them there? wvbaileyWvbailey 02:26, 16 February 2007 (UTC)

I think you are over-analyzing what is essentially a mental construct. It's not necessary to build an ordinary Turing machine to define computability, and it's not necessary that anyone or anything have the ability to put a noncomputable set on the tape of an oracle machine in order to use oracle machines to motivate the definition of relative computability. I have never seen anyone speculate on who or what put the symbols on the tape; it's a question that isn't relevant to computability theory. CMummert · talk 13:02, 16 February 2007 (UTC)
I can't believe that no one would care about this. Wouldn't you agree that the symbols don't "just appear" on the tape by spontaneous generation like the middle-ages belief that meat spontaneously generates flies, hence the consequence of miracles and metaphysics? And given that assertion/belief, if something put the symbols there, then that something is an algorithm operating in the context of a machines that "runs" it (possible exception -- random number generation). Given that all computational machines can be reduced to Turing machines then the oracle is just another plain-vanilla Turing machine... although one is standing outside the "inner" machine's computation: whereas an inner machine may not know it is in a "loop/circle" the outer machine may be able to detect this. (Big woop: the whole enterprise could be shrunk to a single Turing machine, with oracle a subroutine, or vice versa). wvbaileyWvbailey 16:51, 16 February 2007 (UTC)
The oracle is a mathematical abstraction. Its precise nature has not been overlooked; it has been purposefully removed from consideration, because it is unimportant to the results. We remove unimportant features of the model (how the oracle works) so that the model can focus on what is important: the complexity of a certain problem, relative to another known problem.
Additionally, we can think about oracles for noncomputable problems, such as the halting problem, so we can't necessarily assume that everything can be shrunk to a single Turing machine. We can also get interesting results from examining the performance of complexity classes relative to randomly-chosen oracles; there are several reasons that the oracle model is useful. -- Creidieki 21:46, 16 February 2007 (UTC)

We've probably beaten this one to death. There's enough here to write a sage paragraph re "the nature of the oracle", if someone were so inclined. Do you folks agree? Anybody want to take a shot at it? I would like to see Turing's original quote in there, but from there I don't feel confident to continue. You folks clearly know a lot more about this than I do. (The random oracle is interesting. In a lecture I attended some years ago the philosopher Daniel Dennett hypothesized that randomness is the source of "creativity" (he used a "crane lifting itself into the sky" analogy that I've seen elsewhere since); my guess is he would continue on to say that it represents the means by which we can lift ourselves over the "halting problem" barrier.) wvbaileyWvbailey 15:40, 18 February 2007 (UTC)

[edit] Rewording please?

What does "solvable by an algorithm in class A with an oracle for a problem in class B is written AB" mean. I think it needs to be re-worded for clarity. Does it mean "solvable by an oracle-assisted algorithm in class A, for a problem in class B, is written AB"? Does it mean "solvable by an algorithm in class A, with an Class B problem capable oracle, is written AB"? —The preceding unsigned comment was added by 64.180.7.253 (talk) 04:25, 7 February 2007 (UTC).

I Agree with the commentary

In the way it is written the definition is false because it fixes the oracle in B for the whole class A. For example. P^NP is not equal to P^{REACH} where reach is the graph reachability problem. It would make sense if the fixed oracle decides a complete problem in B. But in this case we should assume the existence of complete problems for B, what is not always true.

I would suggest: A problem is in $A^B$ if it can be solved by a turing machine which uses an oracle for some problem in B. (The difference is that now the choosen oracle depends on the problem).

—Preceding unsigned comment added by 131.254.14.172 (talk) 15:51, 22 January 2008 (UTC)