Oracle machine
Definitions

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:

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.
keywords:existence