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)