Talk:Oracle machine

From Wikipedia, the free encyclopedia

You have new messages (last change).

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

[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)
Retrieved from "http://en.wikipedia.org../../../o/r/a/Talk%7EOracle_machine_1116.html"