All Science Fair Projects

Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

Oracle machine

(Redirected from Oracle (computer science))

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 oracle, which is able to decide certain decision problems in a single step. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.

 Contents

Definition

An oracle machine is a Turing machine connected to an oracle. The Turing machine can write on its own tape an input for the oracle, then tell the oracle to execute. In a single step, the oracle computes its function, erases its input, and writes its output to the tape. Sometimes the Turing machine is described as having two tapes, one of which is reserved for oracle inputs and one for outputs.

Complexity classes of Oracle machines

The complexity class of decision problems solvable by an algorithm in class A with an oracle for a problem in class B is written AB. For example, the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for a problem in NP is PNP. (This is also the class of problems reducible by polynomial-time Turing reduction to a problem in NP.)

It is obvious that NP ⊆ PNP, but the question of whether NP ⊂ PNP remains open. See polynomial hierarchy for further extensions.

The notation AB also means the class of problems solvable by an algorithm in class A with an oracle for the language B. For example, PSAT is the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for the Boolean satisfiability problem. When language B is complete for some class C, then AB=AC. In particular, since SAT is NP-complete, PSAT=PNP.

Oracle machines are useful for investigating the relationship between complexity classes P and NP, by considering the relationship between PA and NPA for an oracle A. In particular, it has been shown that there exist languages A and B such that PA=NPA and PB≠NPB (Baker, Gill, Solovay, 1975). When a question such as this has different answers for different oracles, it is said to relativize both ways. The fact that the P=NP question relativizes both ways is taken as evidence that answering this question will be difficult, because any proof technique that relativizes (i.e., is unaffected by the addition of an oracle) will not answer the P=NP question.

It is interesting to consider the case where an oracle is chosen randomly from among all possible oracles. It has been shown that if oracle A is chosen randomly, then with probability 1, PA≠NPA (Bennett, Gill, 1981). When a question is true for almost all oracles, it is said to be true for a random oracle. This is sometimes taken as evidence that P≠NP; unfortunately, it is possible for a statement to be true for a random oracle, but not be true for ordinary Turing machines.

Oracles and Halting Problems

It is possible to posit the existence of an oracle which computes a non-computable function, such as the answer to the halting problem or some equivalent. A machine with an oracle of this sort is a hypercomputer.

Interestingly, the halting paradox still applies to such machines; that is, although they can determine whether particular Turing machines will halt on particular inputs, they cannot determine whether machines with equivalent halting oracles will themselves halt. This fact creates a hierarchy of machines, each with a more powerful halting oracle and an even harder halting problem.

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.

Bibliography

1. Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
2. C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
3. T. P. Baker, J. Gill, R. Solovay. Relativizatons of the P =? NP Question. SIAM Journal on Computing, 4(4): 431-442 (1975)
4. C. H. Bennett, J. Gill. Relative to a Random Oracle A, PA != NPA != co-NPA with Probability 1. SIAM Journal on Computing, 10(1): 96-113 (1981)

The term "oracle machine" is sometimes used to refer to a computer, especially a server, that runs Oracle Corporation's database management system.

03-10-2013 05:06:04
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
Science kits, science lessons, science toys, maths toys, hobby kits, science games and books - these are some of many products that can help give your kid an edge in their science fair projects, and develop a tremendous interest in the study of science. When shopping for a science kit or other supplies, make sure that you carefully review the features and quality of the products. Compare prices by going to several online stores. Read product reviews online or refer to magazines.

Start by looking for your science kit review or science toy review. Compare prices but remember, Price \$ is not everything. Quality does matter.
 Science Fair Coach What do science fair judges look out for? ScienceHound Science Fair Projects for students of all ages
 All Science Fair Projects.com Site All Science Fair Projects Homepage Search | Browse | Links | From-our-Editor | Books | Help | Contact | Privacy | Disclaimer | Copyright Notice