Talk:Oracle machine

Consistency with standard definitions?

The definition of an oracle-machine presented here is interesting, but not clearly poly-time equivalent to the standard (and historical) definition, in which the oracle-tape is read-write, and does not initially encode the characteristic function of the oracle set A, but essentially acts as an input-form for the oracle. In this standard definition, the oracle itself takes the form of a distinguished "query state" q_? of the Turing machine, from which the only transitions are to distinguished "yes" or "no" states, q_yes or q_no, which the Turing machine transitions to depending on whether the oracle tape currently contains an element of A. My question: why is the current definition in terms of a read-only tape containing the characteristic function of A presented instead, and is it clear that these two definitions are poly-time equivalent? 92.231.228.50 (talk) 07:47, 25 August 2010 (UTC)

Example for a particular oracle, please?

I'm having trouble visualizing an oracle machine for which P^B≠NP^B. 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 P^B=NP^B for any oracle, and if P≠NP, then a useless oracle (such as "always outputs zero") would satisfy P^B≠NP^B.

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 P^X is not equal to NP^X. 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 NP^M, 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 P_i be an enumeration of all polynomially-bounded Turing machines, and for each i let p_i(n) be a polynomial that bounds the running time of P_i, as a function of the length of the input string. The goal is to construct a set X such that no P_i accepts L(X). Then L(X) will not be in P^X, but it will be in NP^X, 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 P_i does not accept L(X). Choose n > n(i) so that p_i(n) < 2ⁿ. Run machine P(i) on input 0ⁿ 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 0ⁿ will be accepted by P_i^X 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 0ⁿ will not be accepted by P_i^X but will be in L(X). Note that since p_i(n) < 2ⁿ, 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) = 2ⁿ and go on to the next stage. Note that no string shorter than length 2ⁿ 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 P^X 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 P⁰. 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)

Carl, did this ("about relativizations of P and NP") happen? And if not, do you still think it should happen? yoyo (talk) 07:02, 14 December 2016 (UTC)

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)

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)

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)

• Any decidable problem can be reduced to the Halting problem as follows: Evaluate the original problem; if the answer is true, finish; otherwise keep running forever. If the new machine halts, the original machine returns true, otherwise it either returns false or never stops. Honnza (talk) 11:36, 10 June 2011 (UTC)

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

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)

Rewording please?

What does "solvable by an algorithm in class A with an oracle for a problem in class B is written A^B" 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 A^B"? Does it mean "solvable by an algorithm in class A, with an Class B problem capable oracle, is written A^B"? —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)

Rewrote definition of oracle machine

I completely rewrote the definition of oracle machine. I hope that this is an improvement and answers some of the questions raised in the preceding sections. I'm certainly amenable to further modifications. I didn't take the formal definition from anywhere, but simply made it up to be consistent in style with the definition at Turing machine#Formal definition (but restricted to the case where the alphabet is {1,B}). Some of the texing vs. wiki-formatting may not be ideal; in particular I'm mixing q with $q'$ because I'm not sure how to italicize q' using wiki markup, as the prime confuses the issue. Perhaps I should be using q′? --skeptical scientist (talk) 14:22, 29 July 2008 (UTC)

Your formal definition is clearly wrong. The input alphabet must be different from the tape alphabet otherwise the TM cannot even recognize the end of its input. The definition of the oracle tape seems wrong too. If the TM (with a nonunary alphabet) wants to query the oracle, it must move the oracle head an exponential number of steps in order to check. Thus even if the first part is fixed, your definition is not poly-time equivalent to the standard definition. This should be rewritten, but I'm loath to do so without a reference in front of me. Steve Checkoway (talk) 20:17, 20 December 2012 (UTC)

The issue here is that there are two different notions of an oracle machine and oracle tape:

• The definition usually used in recursion theory has a single work tape and a read-only oracle tape, upon which the oracle set's characteristic function is written. The machine uses the oracle tape to directly read information about the oracle set, and there is no special "query" state. This is the definition in Soare's computability text; a version of this is presented in the article.
• The definition for computational complexity. Here the "oracle tape" is read/write and starts out blank, and the oracle set itself is not written down anywhere. To make a query, the machine writes the string to be queried on the oracle tape and then enters a special "query state". When that state is entered, in one step, the contents of the oracle tape are replaced with the result of the oracle query. This is the definition in Sipser's textbook.

The article should present both of these. The fact that there are two definitions that are wildly different from the point of view of computational complexity is often not noticed, because each student only learns one or the other. — Carl (CBM · talk) 20:31, 20 December 2012 (UTC)

Interesting. I was unaware there were two standard versions that aren't poly-time equivalent. The definition given in the article is still wrong since there is no distinction between input alphabet and tape alphabet with a distinguished blank (and I assume a restriction to unary languages wasn't intended). Steve Checkoway (talk) 07:45, 21 December 2012 (UTC)

Google Books includes a few of the relevant pages of Soare's text. The work tape is given as having two symbols B and 1 while the oracle tape is given as having three symbols B, 0, and 1. Part of the definition of a normal TM isn't available to me in the preview but it does give the work tape as having only two symbols B and 1. So either the input is restricted to be of the form $1^{k}$ for some k or the language $\{w\ |\ w\ {\text{has at least one 1}}\}$ is undecidable. Neither of these options seems reasonable so I must be missing something. Steve Checkoway (talk) 08:29, 21 December 2012 (UTC)

The input is restricted to unary; this is also how Rogers' classic book did it. They ignore the issue of the tape alphabet because they are only concerned with computability, not with computational complexity, and it simplifies the presentation if they don't have to dwell on the alphabet. Also the books are primarily interested in computability of sets of naturals, so strings would only be treated when they are coded by naturals. That approach is common in recursion theory but not at all in complexity theory. — Carl (CBM · talk) 13:52, 21 December 2012 (UTC)

The main reason I have not rewritten it myself is that I have had a hard time finding a good reference for the complexity-theoretic definition in the case where the oracle set consists of strings rather than natural numbers. Sipser leaves out the details, and more classical references like Rogers only deal with sets of naturals. — Carl (CBM · talk) 20:55, 20 December 2012 (UTC)

I don't have my copy of Sipser in front of me (or any book at the moment), but the definition you give for the complexity-theoretic one handles strings just fine: You write the string on the oracle tape and enter the appropriate state. For the recursion-theoretic one, it seems like strings are handled quite simply by giving an arbitrary map $\Sigma \to \{0,1,\ldots ,\#\Sigma -1\}$ and treating the string as a number in base $\Sigma$. Steve Checkoway (talk) 07:45, 21 December 2012 (UTC)

I'm glad I found a definition we can agree on. The main issue with using Sipser as a reference is that his "definition" of an oracle machine is very brief (a couple sentences), and leaves out all the details. It's fine for readers who are willing to fill in the details, but not very useful here where people can be adversarial about trying to literally verify the content to the reference. — Carl (CBM · talk) 13:52, 21 December 2012 (UTC)

Clarification needed

The following statements (both with sources) contradict each other. Someone with access to the sources needs to check them and resolve this.

1. "It has been shown that there exist languages A and B such that P^A=NP^A and P^B≠NP^B."
2. "It has been shown that if oracle A is chosen randomly, then with probability 1, P^A≠NP^A."

If (1) holds, then there is a finite probability that the A of (2) that is chosen is the same as the A of (1). Therefore, the probability given in (2) cannot be exactly 1.0. OrangeDog (τ • ε) 14:13, 20 March 2010 (UTC)

What you say is true if the set of all oracles was a finite set. However, for infinite sets, you can have a probability of exactly 0 of picking some object, even though it exists. For example, consider the real numbers between 0 and 1. If you pick a random real number from this set, with probability 1 it will be irrational. However, we know that there exist rational numbers between 0 and 1. Indeed, there exist infinitely many rationals between 0 and 1. These statements are not contradictory. --Robin (talk) 16:12, 20 March 2010 (UTC)

Ah, I'd overlooked that. Could this clarification be worked into the article? OrangeDog (τ • ε) 18:25, 20 March 2010 (UTC)

I don't know if it can be explained without going into too much math. Even defining precisely what it means to choose an oracle at random requires some basic measure theory. Of course, one could work the particular example I gave into the article, but I'm not sure how much that helps. Feel free to do so, if you wish. --Robin (talk) 19:56, 20 March 2010 (UTC)

I was just about to clarify that it's a choice from an infinite set, when I noticed that there is apparent confusion as to whether we are randomly selecting an oracle, or are selecting a random oracle, or indeed randomly selecting a random oracle. I'm guessing that "(More precisely, a random oracle is constructed by taking every string x to be in the language with probability 1/2.)" should be (re)moved due to explaining an unrelated concept? OrangeDog (τ • ε) 21:25, 20 March 2010 (UTC)

Well, that statement does explain what it means to randomly select an oracle. To continue the previous example, how would one go about picking a uniformly random real number between 0 and 1? One way to do it is to flip infinitely many fair coins, and the first bit of the real is 1 if the first coin comes up heads, and so on. This process (although it never ends) produces a random real number between 0 and 1. Similarly for oracles, an oracle can be chosen at random from the set of all oracles by flipping a fair coin for each string in the language. Perhaps that statement can be made clearer by saying "More precisely, an oracle can be chosen uniformly at random from the set of all oracles by taking every string x to be in the language with probability 1/2." Also, "randomly selecting an oracle" and "selecting a random oracle" sound like the same thing to me. It's like "randomly selecting a ball from an urn" or "selecting a random ball from an urn." If the way I've phrased the part on random oracles sounds confusing, feel free to edit the article to remove the confusion. --Robin (talk) 23:23, 20 March 2010 (UTC)

For clarity, I will refer to the turing definition that uses only two symbols {1,B}. I think there is a conceptual difference between a "random oracle", an oracle that for any input, deterministically returns 1 or B with equal probability, and a "randomly selected oracle", which could for example always return 1. I suspect that for an infinite domain they are mathematically identical (both modelled by a tape with a random binary number on it), but it doesn't help comprehension to switch concepts mid-way through an explanation. To borrow your analogy, compare "angrily selecting a ball from an urn" with "selecting an angry ball from an urn" (if the urn's infinite, there's probably going to be the same amount of anger in both cases :p). I'll see what I can do to clean it up tomorrow, if you haven't got there first.

You are running into an issue with classical probability terminology that is often confusing at first. When people write "for a randomly selected oracle", what they mean is "for a set of oracles of measure 1", and they compensate by talking about probability. So these are equivalent:

• For almost all oracles A, P^A = NP^A
• For a randomly selected oracle A, the probability that P^A = NP^A is 1
• For a sufficiently random oracle A, P^A = NP^A

— Carl (CBM · talk) 12:35, 21 March 2010 (UTC)

Example needed

Hello

As a new student in the field of computer science I am very interested in Turing machines and related "machines" like the Oracle machine. I think this article would be a lot easier to understand for those unfamiliar with the subject if there was a visual example of and Oracle machine solving a problem, a picture (step-by-step pictures or an animated GIF). I'd be glad and grateful should someone provide this. 88.112.51.212 (talk) 13:07, 5 December 2010 (UTC)

An infinite piece of paper with the answer to an uncomputable function written out on it... I'm not sure what kind of useful animation could be created. OrangeDog (τ • ε) 17:21, 5 December 2010 (UTC)

Well, I have seen sample demonstrations of normal Turing machines, why not oracle machines as well? 88.112.51.212 (talk) 14:13, 6 December 2010 (UTC)

It's the same, except for the aforementioned magic tape. OrangeDog (τ • ε) 18:45, 6 December 2010 (UTC)

Wrong definition

As observed on math.se, the definition of oracle machines given in this article is dead wrong. The oracle tape does not contain the characteristic function of the oracle. When the machine needs to access the oracle, it writes the query string to the oracle tape, and enters a query state. In the next step, it continues in one of two states corresponding to whether or not the query string belongs to the oracle. The version given in this article instead forces the machine to use exponential time for each oracle query, which destroys usual oracle complexity classes like NP^A.—Emil J. 18:28, 1 September 2011 (UTC)

The definition here is the one on p. 47 of Soare's book Recursively enumerable sets and degrees, which is the standard textbook for computability theory these days. It may be that people in complexity theory need a different definition, but the one here is not "dead wrong". — Carl (CBM · talk) 20:35, 1 September 2011 (UTC)

What does seem to be wrong is that (1) the article doesn't point out the other definition and (2) the section on complexity theory needs to emphasize that the more efficient definition is needed for the purposes of complexity theory. — Carl (CBM · talk) 20:44, 1 September 2011 (UTC)

Halting Paradox

Assume a programing language that requires that the first thing a program do is to check with the oracle if the program will halt, and then if the oracle says it will halt the program continues, but if the oracle says the program will not halt the program must not go any further. Given those rules the oracle can never answer truthfully, since if the program doesn't halt it is instructed to halt and therefore does so, but then since that would make it halt the program is allowed to continue executing and therefore won't halt. --TiagoTiago (talk) 16:13, 9 November 2011 (UTC)

I think you've confused the program-under-test, call it T, with the procedure P that requests a decision from oracle O. In the following "U" represents a universal Turing machine, Code(T) is the procedure under test, and "code(T's input data)" are the immediate input symbols used by procedure T. " code(P) " is the executable code for a procedure P that requests a decision from oracle O; what follows between brackets [ ] is on the tape. Procedure P includes the printing of the "oracle request", inputting Oracle's response, then halting or executing T. The dots indicate concatenation of “code”. An example is when T is a division algorithm with output (X/Y, R). Will it halt on the input (X=5, Y=0)?

code(P) = code(Hey Oracle, does T halt? If not then halt else execute T)

U: [ code(P)..code(T).code(data for T) ]

Now to the point: Observe that P’s query (to oracle O) about whether algorithm T halts is much different than a query to O about whether or not procedure P itself halts, i.e. the italicized code inside the braces { }:

U: [ code(Hey Oracle, does P halt?)..{ code(Hey Oracle, does P halt?) } ]

U: [ code(P)..code(P) ]

But what if P, after it gets its answer, reverses the decision of the Oracle (e.g. P halts when Oracle says “won’t halt” or P goes into a “tight loop” when Oracle says “will halt”, Oracle cannot answer. Substitute the words “decision procedure” for “Oracle” and you have a proof of the impossibility of the halting problem. This proof can be found in Minsky 1967:148-149, Davis in Steen 1978:256, and Boolos-Burgess-Jeffrey 2002:39. Minsky observes that "It resembles the argument in "Russell's paradox" which forces us to discard arguments concerning "the class of all classes". This proof is different than the diagonalization proof of the halting problem, as observed also by B-B-J: "Finally, it is possible to prove rigourously in another way, not involving d [the "diagonal function"], that h is not Turing computable". The problem derives from "impredicative definitions", input that includes the output as input, e.g. should the unit class (class of all things unitary) include itself in the class? (cf Russell 1903, Goedel's 1943 detailed commentary in Russell's mathematical logic about impredicativity etc in particular his observations about the unit class containing itself, on p. 131). Bill Wvbailey (talk) 15:49, 10 November 2011 (UTC)

Ambiguity in Terminology

In the section "Complexity classes of oracle machines" the terms "P" and "NP" seem to be used to refer to both classes of algorithms and the classes of problems solvable by those algorithms, I guess playing fast and loose in this way is embedded in the conventional terminology, but it should still be clarified because people might wonder how f(x)!=(y) does not imply x!=y. (the answer being that the 'x' and 'y' in the two equations are actually referring to different, but closely related, things by the same name). This led to confusion above in this talk page, but the issue has not been clarified in the article, and I initially came to this talk page over the same confusion. I really think there should be something in the article explaining this. Or even better, change the language to use non-ambiguous terminology, assuming there exists some such alternative convention that is reasonably often used in computer science. 173.227.48.5 (talk) 16:48, 29 June 2012 (UTC)

Definition

Two sections above concern the definition in the article:

• Talk:Oracle_machine#Rewrote_definition_of_oracle_machine
• Talk:Oracle_machine#Wrong_definition

The definition that was here (I didn't write it) was correct, but useless for computational complexity.

I have completely rewritten the section to try to give a more complexity-appropriate definition first, and then give the alternatives later. It took some work to find a reference for a definition that was general enough to cover function problems as well as decision problems, and which could handle multiple symbols on the work tape. But I found at least "some" reference for each definition, which should help with any verifiability concerns.

Please feel free to fix any errors I made or improve the text further. — Carl (CBM · talk) 21:45, 20 December 2012 (UTC)

"left and right" versus "forward and backward"

Should the read head move forward and backward along the tape, not left and right? This needs some clarification. The tape is one instruction wide, so it's not that the read head can move along the width of the tape. And I assume the tape is not a Mobius strip, so it's not able to read any of the symbols backwards. So the terms are chosen to connote the sense that their is no forward direction for the tape? This needs to made explicit.

The "query tape" needs clarification

Please clarify what is meant by "the query tape" in van Melkebeek's definition? It remains unclear to any reader not versed in the jargon exactly which of the two tapes is meant. One approach might be to clarify the notion of "query" - which part of the machine is querying the other? I'm guessing that one approaches an oracle with a question one wants an answer to - but am unsure that's what this means here. yoyo (talk) 17:39, 16 December 2016 (UTC)