Talk:Oracle machine

From Wikipedia, the free encyclopedia

Contents 1 Example for a particular oracle, please? 2 References in Popular Culture 3 Can anyone tell me what "single step" means? 4 Reducing to Halting problems 5 Strange observation re Turing's first proof 6 Nature of the oracle 7 Rewording please?

[edit] 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

[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 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).