This term is used in the book Foundations of Cryptography on pg 20 with regard to defining deterministic oracles, but is not previously defined and I can't seem to find a definition online easily.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
OK, let's first observe the usage of the word in-context:
Definition 1.3.8 (Oracle Machines): A (deterministic/probabilistic) oracle machine is a (deterministic/probabilistic) Turing machine with an additional tape, called the oracle tape, and two special states, called oracle invocation and oracle appeared. The computation of the deterministic oracle machine $M$ on input $x$ and with access to the oracle $f:\{0,1\}^*\to\{0,1\}^*$ is defined by the successive-configuration relation. For configurations with states different from oracle invocation, the next configuration is defined as usual. Let $\gamma$ be a configuration in which the state is oracle invocation and the content of the oracle tape is $q$. Then the configuration following $\gamma$ is identical to $\gamma$ , except that the state is oracle appeared, and the content of the oracle tape is $f(q)$. The string $q$ is called $M$’s query, and $f(q)$ is called the oracle reply. The computation of a probabilistic oracle machine is defined analogously. The output distribution of the oracle machine $M$, on input $x$ and with access to the oracle $f$ , is denoted $M^f(x)$.
So the context we have is: Turing Machines!
Now if we look at the formal definition of a turing machine, we will spot a relation $\delta:(Q\setminus F)\times\Gamma\to Q\times \Gamma\times\{L,R\}$. Note how a function is actually just a relation.
This above function defines, when in a given state and looking at a given cell content, which cell content shall be written, where state shall be entered and which direction the head shall be moved. Thus, this relation defines the successive configuration for every configuration. However I'd guess that the relation used for the turing machine in question is a little bit more complicated than the one of the "basic" turing macine (also accounting for the special states and the extra tape).
