 FACTOID # 18: Alaska spends more money per capita on elementary and secondary education than any other state.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Oracle machine

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 an 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. In computer science, computational complexity theory is the branch of the theory of computation that studies the complexity, or efficiency, of solving computational problems. ... In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. ... An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in Automata theory. ... In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ... An artistic representation of a Turing Machine . ... An oracle is a person or agency considered to be a source of wise counsel or prophetic opinion; an infallible authority, usually spiritual in nature. ... In computational complexity theory, a complexity class is a set of problems of related complexity. ... Undecidable has more than one meaning: In mathematical logic: A decision problem is undecidable if there is no known algorithm that decides it. ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and its initial input, determine whether the program, when executed on this input, ever halts (completes). ...

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. An artistic representation of a Turing Machine . ... An oracle is a person or agency considered to be a source of wise counsel or prophetic opinion; an infallible authority, usually spiritual in nature. ...

## 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.) In computational complexity theory, a complexity class is a set of problems of related complexity. ... In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ... In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. ...

It is obvious that NP ⊆ PNP, but the question of whether NPNP, PNP, NP, and P are equal remains open. See polynomial hierarchy for further extensions. In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines. ...

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. In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... In computational complexity theory, a computational problem is complete for a complexity class when it is, in a formal sense, one of the hardest or most expressive problems in the complexity class. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

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). 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. Diagram of complexity classes provided that P â‰  NP. If P = NP, then all three classes are equal. ... Robert M. Solovay is a set theorist who spent many years as a professor at UC Berkeley. ...

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, a statement may be true for a random oracle and false for ordinary Turing machines at the same time. A random oracle is a mathematical abstraction used in cryptographic proofs. ...

## 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. In computability theory computable functions or Turing computable functions are the basic objects of study. ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and its initial input, determine whether the program, when executed on this input, ever halts (completes). ... Hypercomputation is the law of methods for the computation of non-computable functions. ...

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, called the arithmetical hierarchy, each with a more powerful halting oracle and an even harder halting problem. In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene hierarchy classifies the set of arithmetic formulas (or arithmetic sets) according to their degree of solvability. ...

## Applications to Cryptography

One of the common uses of oracles in modern computer science is in cryptographic protocols. If we suppose the existence of a random oracle that gives a random (but consistent) string in response to any question, then this gives a sort of super-secure one-way function. That is, given an output of the oracle, it is impossible for any program to find an input producing that output, except by trying lots of inputs. This leads to very strong protocols, but to implement the protocols in practice the random oracles are usually replaced by a pseudorandom generator. Unfortunately, this is in general not as secure. See random oracle for more details. A random oracle is a mathematical abstraction used in cryptographic proofs. ... Unsolved problems in computer science: Do one-way functions exist? A one-way function is a function that is easy to calculate but hard to invert â€” it is difficult to calculate the input to the function given its output. ... Let G be a deterministic polynomial time function from N<Ï‰ to N<Ï‰ with stretch function l:N â†’ N, so that if x has length n then G(x) has length l(n). ... A random oracle is a mathematical abstraction used in cryptographic proofs. ...

## Nature of the oracle

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.

## Bibliography

1. Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
2. C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Section 14.3: Oracles, pp. 339 – 343.
3. T. P. Baker, J. Gill, R. Solovay. Relativizations 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)
5. Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 9.2: Relativization, pp.318 – 321.
6. Martin Davis, editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. Turing's paper is in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post. Results from FactBites:

 The Oracle War (6796 words) Despite the beliefs and devotion of the Mystery Cultists the Oracle Machines themselves never claimed to have prognostic powers of any sort, and most godwatchers and toposophologists are of the opinion that they simply used their superior toposophic levels to maintain an illusion of accuracy in prediction. The Oracle machines were well known for their skill in predicting the short term future, particularly in markets and social trends; this brought some benefits to the Enthralled population of this small paraterraformed world with half a billion inhabitants, but also brought benefits to the population in general. Machines seemed to have the upper hand; after the Ascension of Binah and the entry of the Negentropists and Keterists the tide turned, and the war became a long process of attrition and decontamination.
 Oracle machine - Wikipedia, the free encyclopedia (881 words) An oracle machine is a Turing machine connected to an oracle. Oracle machines are useful for investigating the relationship between complexity classes P and NP, by considering the relationship between P A machine with an oracle of this sort is a hypercomputer.
More results at FactBites »

Share your thoughts, questions and commentary here
Press Releases | Feeds | Contact