Oracle machine

Definition

An oracle machine is a Turing machine with these extra parts:

1. a second tape, the oracle tape, on which the machine can read and write;
2. three special states: a query state $q_?$, a yes state $q_{\mathrm{yes}}$ and a no state $q_{\mathrm{no}}$.

Let $O \subseteq \N$ be a set, the oracle. The machine $M$ with oracle $O$, written $M^O$, runs like a Turing machine, except at the query state. Suppose $M^O$ enters $q_?$ while the oracle tape holds the binary code of a number $n$. Then its next state is $q_{\mathrm{yes}}$ if $n \in O$ and $q_{\mathrm{no}}$ if $n \notin O$. A partial function $f \colon \N \to \N$ is computable relative to $O$ if there is an oracle machine $M$ with this property. For every $x$, the run of $M^O$ on input $x$ halts with output $f(x)$ when $f(x)$ is defined, and does not halt otherwise.