This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(October 2023) (Learn how and when to remove this message)

Black box systems
System
Black box,Oracle machine
Methods and techniques
Black-box testing,Blackboxing
Related techniques
Feed forward,Obfuscation,Pattern recognition,White box,White-box testing,Gray-box testing,System identification
Fundamentals
A priori information,Control systems,Open systems,Operations research,Thermodynamic systems
v t e

Incomplexity theory andcomputability theory, anoracle machine is anabstract machine that can query ablack box called anoracle, 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 anycomplexity class, or it can even be anundecidable problem such as thehalting problem. If another problem⁠${\displaystyle R^{\prime }}$⁠ isreducible to⁠${\displaystyle R}$⁠ inpolynomial time, then the oracle machine (with the⁠${\displaystyle R}$⁠-oracle) can solve⁠${\displaystyle R^{\prime }}$⁠ in polynomial time; one can say that⁠${\displaystyle R^{\prime }}$⁠ is in therelativized complexity class⁠${\displaystyle {\mathsf{P}}^R}$⁠. Other relativized complexity classes such as⁠${\displaystyle {\mathsf{N}\mathsf{P}}^R}$⁠ can be defined analogously.^[1]

An oracle machine can be conceived as aTuring machine connected to anoracle. The oracle, in this context, is an entity capable of solving some problem, which for example may be adecision problem or afunction 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 givencomputational problem:

• A decision problem is represented as a setA ofnatural numbers (orstrings). 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 abinary relationR relating natural numbers (or strings) to natural numbers (or strings). An instance of the problem is an inputx forR. A solution is a value related tox byR.

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 setA 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 ofA.

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

An oracle machine, like a Turing machine, includes:

• awork 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;
• aread/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;
• acontrol mechanism, which can be in one of a finite number ofstates, 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:

• anoracle 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.
• anoracle 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 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:

• Some definitions, instead of writing the answer to the oracle tape, have two special states YES and NO in addition to the ASK state. When the oracle is consulted, the next state is chosen to be YES if the contents of the oracle tape are in the oracle set, and chosen to be NO if the contents are not in the oracle set.^[2]
• Some definitions eschew the separate oracle tape. When the oracle state is entered, a tape symbol is specified. The oracle is queried with the number of times that this tape symbol appears on the work tape. If that number is in the oracle set, the next state is the YES state; if it is not, the next state is the NO state.^[3]
• Another alternative definition makes the oracle tape read-only, and eliminates the ASK and RESPONSE states entirely. Before the machine is started, theindicator function of the oracle set is written on the oracle tape using symbols 0 and 1. The machine is then able to query the oracle by scanning to the correct square on the oracle tape and reading the value located there.^[4]

These definitions are equivalent from the point of view of Turing computability: a function is oracle-computable from a given oracle under all of these definitions if it is oracle-computable under any of them. The definitions are not equivalent, however, from the point of view ofcomputational complexity. A definition such as the one by van Melkebeek, using an oracle tape that may have its own alphabet, is required in general.

Thecomplexity class ofdecision problems solvable by an algorithm in classA with an oracle for a languageL is calledA^L. For example, P^SAT is the class of problems solvable inpolynomial time by adeterministic Turing machine with an oracle for theBoolean satisfiability problem. The notation A^B can be extended to a set of languagesB (or a complexity classB), by using the following definition:

${\displaystyle A^B=\bigcup _{L\in B}{A}^L}$

When a languageL iscomplete for some classB, thenA^L=A^B provided that machines inA can execute reductions used in the completeness definition of classB. In particular, since SAT isNP-complete with respect to polynomial time reductions, P^SAT=P^NP. However, ifA =DLOGTIME, thenA^SAT may not equalA^NP. (The definition of${\displaystyle A^B}$ given above is not completely standard. In some contexts, such as the proof of thetime andspace hierarchy theorems, it is more useful to assume that the abstract machine defining class${\displaystyle A}$ only has access to a single oracle for one language. In this context,${\displaystyle A^B}$ is not defined if the complexity class${\displaystyle B}$ does not have any complete problems with respect to the reductions available to${\displaystyle A}$.)

It is understood that NP ⊆ P^NP, but the question of whether NP^NP, P^NP, NP, and P are equal remains tentative at best. It is believed they are different, and this leads to the definition of thepolynomial hierarchy.

Oracle machines are useful for investigating the relationship betweencomplexity classes P and NP, by considering the relationship between P^A and NP^A for an oracleA. In particular, it has been shown there exist languagesA andB such that P^A=NP^A and P^B≠NP^B.^[5] The fact the P = NP question relativizes both ways is taken as evidence that answering this question is difficult, because any proof technique thatrelativizes (i.e., is unaffected by the addition of an oracle) will not answer the P = NP question.^[6] Most proof techniques relativize.^[7]

One may consider the case where an oracle is chosen randomly from among all possible oracles (aninfinite set). It has been shown in this case, that with probability 1, P^A≠NP^A.^[8] When a question is true for almost all oracles, it is said to be truefor arandom oracle. This choice of terminology is justified by the fact that random oracles support a statement with probability 0 or 1 only. (This follows fromKolmogorov's zero–one law.) This is only weak evidence that P≠NP, since a statement may be true for a random oracle but false for ordinary Turing machines; for example, IP^A≠PSPACE^A for a random oracleA butIP =PSPACE.^[9]

A machine with an oracle for thehalting problem can determine whether particular Turing machines will halt on particular inputs, but it cannot determine, in general, whether oracle machines like itself (i.e. equipped with an oracle for the halting problem) will halt. This creates a hierarchy of machines, each with a more powerful halting oracle and an even harder halting problem.This hierarchy of machines can be used to define thearithmetical hierarchy.^[10]

Incryptography, oracles are used to make arguments for the security ofcryptographic protocols where ahash function is used. Asecurity reduction (proof of security) for the protocol is given in the case where, instead of a hash function, arandom oracle answers each query randomly but consistently; the oracle is assumed to be available to all parties including the attacker, as the hash function is. Such a proof shows that unless the attacker solves the hard problem at the heart of the security reduction, they must make use of some interesting property of the hash function to break the protocol; they cannot treat the hash function as a black box (i.e., as a random oracle).

• Computability theory
• Turing machine
• Computation oracles

• Articles with short description
• Short description matches Wikidata
• Articles lacking in-text citations from October 2023
• All articles lacking in-text citations
• Use dmy dates from October 2023
• CS1 maint: DOI inactive as of July 2025