home | alphabetical index | |||||||

## Oracle machineIn complexity theory and computability theory, anoracle is a black box that computes a function in a single step. This could be a function solving an NP-complete problem such as the subset sum problem. It could even be an "uncomputable" (non-recursive) function like the halting problem.
## Oracle machines
An ## Oracles and Complexity Theory
Clearly, for some oracles, the oracle machine will be more powerful than a simple Turing machine. It is possible to define complexity classes analogous to
For an oracle
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 ## Oracles and Halting ProblemsIt is possible to posit the existence of an oracle which computes a non-recursive 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 CultureThe 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.
The term "oracle machine" is sometimes used to refer to a computer, especially a server, that runs Oracle Corporation's database management system. | |||||||

copyright © 2004 FactsAbout.com |