Oracle (computer science)
| Black box systems | |
|---|---|
 |
|
| Concepts | |
| Black box · Oracle machine | |
| Methods and techniques | |
|
Black-box testing · Blackboxing
|
|
| Related techniques | |
|
Feed forward · Obfuscation Pattern recognition · White box System identification |
|
| Fundamentals | |
|
Control systems · Open systems Operations research Thermodynamic systems |
|
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 solve certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used.
An oracle machine can be conceived as a Turing machine connected to an oracle. The oracle, in this context, is an entity capable of solving some problem, which for example may be a decision problem or a function problem. The problem does not have to be computable; the oracle is not assumed to be a Turing machine or computer program. The oracle is simply a "black box" that is able to produce a solution for any instance of a given computational problem:
An oracle machine can perform all of the usual operations of a Turing machine, and can also query the oracle to obtain a solution to any instance of the computational problem for that oracle. For example, if the problem is a decision problem for a set A of natural numbers, the oracle machine supplies the oracle with a natural number, and the oracle responds with "yes" or "no" stating whether that number is an element of A.
There are many equivalent definitions of oracle Turing machines, as discussed below. The one presented here is from van Melkebeek (2000:43).
An oracle machine, like a Turing machine, includes:
In addition to these components, an oracle machine also includes:
From time to time, the oracle machine may enter the ASK state. When this happens, the following actions are performed in a single computational step:
The effect of changing to the ASK state is thus to receive, in a single step, a solution to the problem instance that is written on the oracle tape.
There are many alternative definitions to the one presented above. Many of these are specialized for the case where the oracle solves a decision problem. In this case:
...
Wikipedia