Oracle Turing Machine

computation

Definition

Oracle Turing Machine

Let $A\subseteq {\Sigma }^{\ast }$ be a language (the oracle). An oracle Turing machine for $A$ is a multitape Turing machine $M$ equipped with a distinguished query tape and three special states $q_{ask},q_{yes},q_{no}$ such that:

1. During a computation on input $x$, $M$ may enter $q_{ask}$. The string currently written on the query tape is interpreted as a query $y$.

2. In one abstract step, the machine is moved without changing any other tape contents (except possibly the head positions specified by the transition) to:

• $q_{yes}$ if $y\in A$

• $q_{no}$ if $y\notin A$

1. $M$ otherwise behaves like an ordinary Turing machine.

We write $M^A$ for $M$ with oracle $A$. The language decided by $M^A$ is:

$$L(M^A)=\{x\mid M^A\text{halts on}x\text{in an accepting state}\}$$

Time measure: Unless stated otherwise, each oracle call counts as one unit of time. The running time of $M^A$ on $x$ is the number of ordinary steps plus the number of oracle calls.