It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a single operation.

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.

A definition such as the one by van Melkebeek, using an oracle tape which may have its own alphabet, is required in general.

The complexity class of decision problems solvable by an algorithm in class A with an oracle for a language L is called AL. 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.

In some contexts, such as the proof of the time and space hierarchy theorems, it is more useful to assume that the abstract machine defining class

This choice of terminology is justified by the fact that random oracles support a statement with probability 0 or 1 only.

This is only weak evidence that P≠NP, since a statement may be true for a random oracle but false for ordinary Turing machines;[original research?]

[9] In cryptography, oracles are used to make arguments for the security of cryptographic protocols where a hash function is used.

A security reduction (proof of security) for the protocol is given in the case where, instead of a hash function, a random 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).