Oracle machine - Wikipedia

Jump to content

Search

Search

Donate

Create account

Log in

Personal tools

Donate

Create account

Log in

Oracle machine

16 languages

Català<br>Deutsch<br>Español<br>فارسی<br>Suomi<br>Français<br>עברית<br>日本語<br>한국어<br>Polski<br>Português<br>Русский<br>Српски / srpski<br>Türkçe<br>Українська<br>中文

Edit links

From Wikipedia, the free encyclopedia

Abstract machine used to study decision problems

For computing equipment sold by Oracle Corporation, see Oracle Corporation § Hardware.

This article includes a list of general references, but it lacks sufficient corresponding inline citations . Please help to improve this article by introducing more precise citations. (October 2023) (Learn how and when to remove this message)

Black box systemsSystemBlack box, Oracle machineMethods and techniquesBlack-box testing, Blackboxing Related techniquesFeed forward, Obfuscation, Pattern recognition, White box, White-box testing, Gray-box testing, System identificationFundamentalsA priori information, Control systems, Open systems, Operations research, Thermodynamic systemsv

In complexity theory and computability theory, an oracle machine is an abstract machine that can query a black box called an oracle , which is able to give an answer to any instance of a certain problem ⁠

{\displaystyle R}

⁠ in a single operation. The problem ⁠

{\displaystyle R}

⁠ can be of any complexity class, or it can even be an undecidable problem such as the halting problem. If another problem ⁠

{\displaystyle R'}

⁠ is reducible to ⁠

{\displaystyle R}

⁠ in polynomial time, then the oracle machine (with the ⁠

{\displaystyle R}

⁠-oracle) can solve ⁠

{\displaystyle R'}

⁠ in polynomial time; one can say that ⁠

{\displaystyle R'}

⁠ is in the relativized complexity class ⁠

{\displaystyle {\mathsf {P}}^{R}}

⁠. Other relativized complexity classes such as ⁠

{\displaystyle {\mathsf {NP}}^{R}}

⁠ can be defined analogously.[1]

Oracles<br>[edit]

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:

A decision problem is represented as a set A of natural numbers (or strings). An instance of the problem is an arbitrary natural number (or string). The solution to the instance is "YES" if the number (string) is in the set, and "NO" otherwise.

A function problem is represented by a binary relation R relating natural numbers (or strings) to natural numbers (or strings). An instance of the problem is an input x for R. A solution is a value related to x by R.

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.

Definitions<br>[edit]

There are many equivalent definitions of oracle Turing machines, as discussed below. The one presented here is from van Melkebeek (2003, p. 43).

An oracle machine, like a Turing machine, includes:

a work tape : a sequence of cells without beginning or end, each of which may contain a B (for blank) or a symbol from the tape alphabet;

a read/write head , which rests on a single cell of the work tape and can read the data there, write new data, and increment or decrement its position along the tape;

a control mechanism , which can be in one of a finite number of states , and which will perform different actions (reading data, writing data, moving the read/write head, and changing states) depending on the current state and the data being read.

In addition to these components, an oracle machine also includes:

an oracle tape , which is a semi-infinite tape separate from the work tape. The alphabet for the oracle tape may be different from the alphabet for the work tape.

an oracle head which, like the read/write head, can move left or right along the oracle tape reading and writing symbols;

two special states: the ASK state and the RESPONSE state.

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 contents of the oracle tape are viewed as an instance of the oracle's computational problem;

the oracle is consulted, and the contents of the oracle tape are replaced with the solution to that instance of the problem;

the oracle head is moved to the first square on the oracle tape;

the state of the oracle machine is changed to RESPONSE.

The effect of changing...