Definition:Oracle Machine

This article needs to be linked to other articles. In particular: category for a start You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

Definition

An oracle machine is an extension of a Turing machine with an additional capability.

In addition to manipulating the symbols on its tape (or tapes, in the case of a multitape Turing machine), it can determine if a value belongs to a given language $T$ in a single step.

Formal Definition

Let $k \in \N_{> 0}$.

Let $M = \struct {Q, \Sigma, \Gamma, \delta, q_0, B, F}$ be a $k + 1$-tape Turing machine.

Let $q_q, q_y, q_n \in Q$.

$q_q$ is the query state

$q_y$ is the yes state

$q_n$ is the no state

Suppose that, for all $s_1, \dotsc, s_k, s_{k + 1} \in \Gamma$:

$\map \delta {q_q, s_1, \dotsc, s_k, s_{k + 1}}$ is undefined.

Let $T \subseteq \Gamma^*$ be a formal language over the alphabet $\Gamma$.

Then, the oracle machine $M$ relative to the language $T$ is denoted as $M^T$.

The instantaneous descriptions of $M^T$ are precisely the instantaneous descriptions of $M$.

Given instantaneous descriptions $A, B$, we write $A \vdash B$ if and only if either:

$A \vdash_M B$, that is $A \vdash B$ in the context of the multitape Turing machine $M$

or:

$A_i = B_i$ for each $1 \le i \le k$

$A_{k + 1} = \alpha q_q \beta$

$\alpha \beta = B \dotsm B \gamma B \dotsm B$, where $\gamma$ does not start or end with $B$

If $\gamma \in T$, then $B_{k + 1} = \alpha q_y \beta$

If $\gamma \notin T$, then $B_{k + 1} = \alpha q_n \beta$

That is, a step in $M^T$ is either a usual step of the underlying multitape Turing machine, or a transition to state $q_y$ or $q_n$ depending on whether the $k + 1$-th tape's contents belong to $T$.

Then, in the same manner as for multitape Turing machine, we define:

$A \vdash^* B$

if and only if there exists a sequence $\sequence {A_i}_{0 \le i \le n}$ such that:

$A = A_0 \vdash A_1 \vdash \dotso \vdash A_{n - 1} \vdash A_n = B$

The language $\map L {M^T}$ accepted by the machine $M^T$ is the set of strings $w \in \Sigma^*$ such that:

$\tuple {q_0 w; q_0 B; \dotsc; q_0 B; q_0 B} \vdash^* \tuple {\alpha_1 q_f \beta_1, \dotsc, \alpha_k q_f \beta_k, \alpha_{k + 1} q_f \beta_{k + 1}}$

where:

$\alpha_1, \dotsc, \alpha_k, \alpha_{k + 1}, \beta_1, \dotsc, \beta_k, \beta_{k + 1} \in \Gamma^*$

$q_f \in F$

As a special case, the null string is in $\map L {M^T}$ if and only if the above holds for $w = B$.

The machine $M^T$ halts on an input $w$, using the same special case for the null string as above, if and only if:

$\tuple {q_0 w; q_0 B; \dotsc; q_0 B; q_0 B} \vdash^* \tuple {\alpha_1 q X_1 \beta_1, \dotsc, \alpha_k q X_k \beta_k, \alpha_{k + 1} q X_{k + 1} \beta_{k + 1}}$

where:

$X_1, \dotsc, X_k, X_{k + 1} \in \Gamma$

$\alpha_1, \dotsc, \alpha_k, \alpha_{k + 1}, \beta_1, \dotsc, \beta_k, \beta_{k + 1} \in \Gamma^*$

$\map \delta {q, X_1, \dotsc, X_k, X_{k + 1}}$ is undefined

Sources

• 1971: Stephen A. Cook: The Complexity of Theorem-Proving Procedures (STOC Ser. '71 : pp. 151 – 158) (in which Cook-Levin Theorem is presented)