Computation relative to an oracle

A non-computable set can be seen as an unsolvable problem. To compare unsolvable problems with one another, Turing introduced in 1939 machines that may consult an oracle: a set $X \subseteq \nat$, given as an infinite external resource, which the machine may query at any time for the value of $X(n)$. A set is then computable relative to $X$ if some oracle machine decides it with oracle $X$. This lesson defines oracle computations, proves the property that makes them manageable — a halting computation consults only finitely many bits of the oracle — and shows that the basic results of the course on fundamentals hold relative to any oracle.

1.1 Strings and sequences

We use the notation of Definition 4.1 of “The diagonal argument”. A string is an element $\sigma$ of $\bstr$, the set of finite binary sequences; $|\sigma|$ is its length, $\sigma(n)$ its $n$-th bit for $n < |\sigma|$, and $\varepsilon$ the empty string. For strings $\sigma$ and $\tau$ and $X \in \cs$:

• $\sigma \preceq \tau$ means that $\sigma$ is a prefix of $\tau$, and $\sigma \prec X$ that $\sigma$ is a prefix of $X$;
• $\sigma$ and $\tau$ are compatible if one is a prefix of the other, and incompatible otherwise;
• $\sigma \tau$ and $\sigma i$ denote concatenations, for $i \in \{0, 1\}$, and $X \uh n = X(0) \cdots X(n-1)$;
• $[\sigma] = \{ X \in \cs : \sigma \prec X \}$ is the cylinder of $\sigma$.

Strings are coded by integers in a fixed computable way, so that the usual operations on them are primitive recursive. Sets of integers are identified with elements of $\cs$.

1.2 Oracle machines

Definition 1.1.#

An oracle machine is a Turing machine with a second, read-only tape, the oracle tape, whose cells are indexed by $\nat$, and a second head on it, starting on cell $0$. Its transition function has the form

$$\delta : (Q \setminus \{ q_h \}) \times \Gamma \times \{0, 1\} \to Q \times \Gamma \times \{L, R\} \times \{L, S, R\}:$$

in state $q$, reading $a$ on the work tape and $b$ under the oracle head, the machine writes $a'$ on the work tape, moves the work head in direction $D$ and the oracle head in direction $D'$ ($S$ meaning that it stays; a move to the left from cell $0$ leaves it on cell $0$), and enters the state $q'$, where $\delta(q, a, b) = (q', a', D, D')$.

With oracle $X \in \cs$, the oracle tape contains $X(k)$ on cell $k$. Inputs and outputs follow the conventions of Definition 2.4 of “Turing machines”.

An oracle machine computes, for each oracle $X$, a partial function $\nat^k \rightharpoonup \nat$. Ordinary Turing machines are the oracle machines that ignore their oracle. Oracle machines are coded by integers as ordinary machines are; the integers that are not codes are treated as coding a machine that never halts.

Definition 1.2.#

For $e, k \in \nat$, the Turing functional $\Phi_e$ is the map which sends an oracle $X$ to the partial function $\Phi^X_e : \nat^k \rightharpoonup \nat$ computed by the oracle machine of code $e$ with oracle $X$. We also write $\Phi_e(X, \vec x)$ for $\Phi_e^X(\vec x)$.

The notation is consistent with the course on fundamentals once a convention is fixed: from now on, $\Phi_e$ denotes the functional of index $e$, and when no oracle is written, $\Phi_e(x)$ stands for $\Phi^{\emptyset}_e(x)$, $\Phi_e(x)[s]$ for $\Phi^{\emptyset}_e(x)[s]$ (defined below) and $W_e$ for $\dom(\Phi^{\emptyset}_e)$. The partial computable functions of that course are exactly the functions $\Phi^{\emptyset}_e$, or $\Phi^X_e$ for any computable $X$ (see the exercises), although a function need not have the same indices in the two enumerations. Since every ordinary machine is an oracle machine, every partial computable function is $\Phi^X_e$ for some $e$ and every $X$.

Example 1.3.#

Let $X$ be an infinite set whose principal function $p_X$ (Lemma 3.2 of “Countable sets”) grows fast enough that $\Phi_e(e)\converge$ implies $\Phi_e(e)[p_X(e)]\converge$, for every $e$. Then there is an oracle machine computing $\emptyset'$ with oracle $X$: on input $e$, read the oracle until its $e$-th element $p_X(e)$ is found, then run $\Phi_e(e)$ for $p_X(e)$ stages, and answer $1$ if and only if it has converged. Fast-growing sets can thus compute the halting set; this phenomenon is studied in the lesson on limit computability.

1.3 Computations with finite oracles

A halting computation is finite, so it reads only finitely many cells of the oracle. This is the basis of everything that follows. For a string $\sigma$, the computation with oracle $\sigma$ is the computation of the machine in which the oracle tape contains $\sigma(k)$ on the cells $k < |\sigma|$; it is considered undefined as soon as the oracle head reaches a cell $k \geq |\sigma|$.

Definition 1.4.#

For $\sigma \in \bstr$, $e, x, s \in \nat$:

1. $\Phi^\sigma_e(x)\converge = y$ means that the computation of the machine $e$ on input $x$ with oracle $\sigma$ halts in a standard configuration with output $y$, without the oracle head reaching a cell $k \geq |\sigma|$;
2. $\Phi^\sigma_e(x)[s]\converge = y$ means that moreover $e, x < s$ and the code of this computation is smaller than $s$;
3. for $X \in \cs$, $\Phi^X_e(x)[s] \simeq \Phi^{X \uh s}_e(x)[s]$.

As in Kleene's normal form, the relation ”$t$ codes a halting computation of the machine $e$ on input $x$ with oracle $\sigma$” is primitive recursive in $(\sigma, e, x, t)$: configurations now include the position of the oracle head, and each step consults one bit of $\sigma$, available since $\sigma$ is part of the data. A computation of code $t$ has fewer than $t$ steps, and the oracle head moves at most one cell per step, so it reads only cells $k < t$.

Proposition 1.5.#

1. The relation $\Phi^\sigma_e(x)[s]\converge = y$ is primitive recursive in $(\sigma, e, x, s, y)$.
2. Monotonicity. If $\Phi^\sigma_e(x)[s]\converge = y$, $\sigma \preceq \tau$ and $s \leq s'$, then $\Phi^\tau_e(x)[s']\converge = y$.
3. Approximation. For every $X \in \cs$: $\Phi^X_e(x)\converge = y$ if and only if $\Phi^X_e(x)[s]\converge = y$ for some $s$, if and only if $\Phi^\sigma_e(x)\converge = y$ for some $\sigma \prec X$.

Proof of Proposition 1.5.

1. $\Phi^\sigma_e(x)[s]\converge = y$ holds if and only if $e, x < s$ and some $t < s$ codes a halting computation of $e$ on $x$ with oracle $\sigma$, with output $U(t) = y$: a bounded quantification of a primitive recursive relation.
2. The computation with oracle $\sigma$ reads only cells $k < |\sigma|$, where $\tau$ agrees with $\sigma$; so with oracle $\tau$ the machine performs the same steps, and the computation has the same code.
3. If $\Phi^X_e(x)\converge = y$, let $t$ be the code of the computation with oracle $X$. It reads only cells $k < t$, so it is also the computation with oracle $X \uh t$, and $\Phi^X_e(x)[s]\converge = y$ for $s = \max(e, x, t) + 1$, since $X \uh t \preceq X \uh s$. If $\Phi^X_e(x)[s]\converge = y$, then $\sigma = X \uh s$ works. Finally, if $\Phi^\sigma_e(x)\converge = y$ with $\sigma \prec X$, the computation with oracle $X$ performs the same steps, by the argument of item 2.

Definition 1.6.#

If $\Phi^X_e(x)\converge$, the use of the computation, written $\use^X_e(x)$, is $1$ plus the largest cell read by the oracle head during the computation (the head reads cell $0$ initially, so the use is at least $1$).

Theorem 1.7 (Use principle).#

If $\Phi^X_e(x)\converge = y$ with use $u$, then $\Phi^Y_e(x)\converge = y$, with the same use, for every $Y$ such that $Y \uh u = X \uh u$. In particular $\Phi^{X \uh u}_e(x)\converge = y$.

Proof of Theorem 1.7.

By induction on the number of steps, the computations with oracles $X$ and $Y$ pass through the same configurations: the oracle head stays within the cells $k < u$ during the computation with oracle $X$, and there $X$ and $Y$ agree, so each step reads the same oracle bit. Hence the computation with oracle $Y$ halts after the same number of steps, with the same output, and reads the same cells. The last statement is the same argument with the finite oracle $X \uh u$, of length $u$.

The use principle says that the value of a convergent computation depends only on a finite part of the oracle. In topological terms, which are developed in the course on $\Pi^0_1$ classes, the partial map $X \mapsto \Phi^X_e(x)$ is continuous on its domain, for the product topology on $\cs$: if $\Phi^X_e(x)\converge = y$, then $\Phi^Y_e(x)\converge = y$ on the whole open neighborhood $[X \uh u]$ of $X$.

1.4 Relativization

Definition 1.8.#

Let $X \in \cs$. A partial function is $X$-computable, or computable in $X$, if it is $\Phi^X_e$ for some $e$. A set is $X$-computable if its characteristic function is. A set is $X$-computably enumerable, or $X$-c.e., if it is the domain of an $X$-computable partial function; we write $W^X_e = \dom(\Phi^X_e)$.

Every argument of the course on fundamentals is an algorithm, or a construction of algorithms, and remains valid if all machines are given access to the same oracle $X$. This relativization yields, for each theorem, a version relative to $X$, obtained by replacing computable with $X$-computable and $\Phi_e$ with $\Phi^X_e$ throughout. For instance, relative to $X$, the c.e. sets are characterized as in Theorem 4.3 of “Computably enumerable sets”, a set is $X$-computable if and only if it and its complement are $X$-c.e., and the fixed point theorem holds for $X$-computable transformations of indices. Two results deserve to be stated explicitly, because their relativized form is uniform: the objects they provide do not depend on $X$.

Theorem 1.9 (Relativized universal function).#

There is an index $u$ such that $\Phi^X_u(e, x) \simeq \Phi^X_e(x)$ for every $X$, $e$ and $x$.

Proof of Theorem 1.9.

By Proposition 1.5, $\Phi^X_e(x) \simeq U\big(\mu t\ T(X \uh t, e, x, t)\big)$, where $T(\sigma, e, x, t)$ is the primitive recursive relation ”$t$ codes a halting computation of $e$ on $x$ with oracle $\sigma$”. An oracle machine computes this expression: on input $(e, x)$, for $t = 0, 1, 2, \dots$, it reads $X \uh t$ on its oracle tape, and tests the relation. The same machine works for every oracle.

Theorem 1.10 (Relativized SMN theorem).#

For all $m, n \geq 1$, the primitive recursive function $S^m_n$ of SMN theorem satisfies, for every oracle $X$,

$$\Phi^X_{S^m_n(e, \vec x)}(\vec y) \simeq \Phi^X_e(\vec x, \vec y).$$

Proof of Theorem 1.10.

The construction of SMN theorem prepends to the machine $e$ a machine writing $\vec x$ on the work tape, without touching the oracle head. The resulting oracle machine first writes $\vec x$, then behaves as the machine $e$, with the same oracle; this does not depend on the oracle.

The function $S^m_n$ is computable, not merely $X$-computable: it manipulates codes of machines and never consults the oracle. Uniformity of this kind is used repeatedly, for instance to show that the jump is monotone. In proofs, we use the parameter form: if $f(X, x, \vec y)$ is computed by an oracle machine, there is a computable $s$ with $\Phi^X_{s(x)}(\vec y) \simeq f(X, x, \vec y)$ for every $X$.

Remark 1.11 (Relativization in complexity theory).#

Almost all proofs of computability theory relativize. In complexity theory, this is a limitation: Baker, Gill and Solovay constructed oracles $A$ and $B$ with $\mathrm{P}^A = \mathrm{NP}^A$ and $\mathrm{P}^B \neq \mathrm{NP}^B$, so no relativizing argument can settle the question $\mathrm P = \mathrm{NP}$. We admit this result.

1.5 Oracles that are functions

A function $f : \nat \to \nat$ can also serve as an oracle, through its graph: let $G_f = \{ \langle x, y \rangle : f(x) = y \}$, a subset of $\nat$. A machine with oracle $G_f$ can compute $f(x)$ by searching for the $y$ with $\langle x, y \rangle \in G_f$; conversely, a machine that can compute $f$ can decide $G_f$. We say that a set or a function is $f$-computable if it is $G_f$-computable. Computing with an oracle $f$ is therefore computing with the ability to evaluate $f$ at any point.

1.6 Exercises

Exercise 1.12 ★.

Show that if $X$ is computable, then the $X$-computable partial functions are exactly the partial computable functions.

Solution

A partial computable function is computed by a machine that ignores its oracle. Conversely, let $X = \Phi_c$ be computable and let $f = \Phi^X_e$. Replace each consultation of the oracle tape at cell $k$ by a computation of $\Phi_c(k)$; more precisely, $f(x) \simeq U(\mu t\ T(\sigma_t, e, x, t))$ where $\sigma_t = \Phi_c(0) \cdots \Phi_c(t-1)$ is computable from $t$. This expression is partial computable.

Exercise 1.13 ★.

Show that the partial function $(X, e, x) \mapsto \use^X_e(x)$ is computed by an oracle machine: there is $v$ with $\Phi^X_v(e, x) \simeq \use^X_e(x)$ for every $X$, $e$ and $x$.

Solution

On input $(e, x)$ with oracle $X$, search for the least $t$ with $T(X \uh t, e, x, t)$, as in Theorem 1.9; the computation coded by $t$ is then known, and the use is $1$ plus the largest oracle head position appearing in its configurations. If $\Phi^X_e(x)\diverge$, the search diverges, as it should.

Exercise 1.14 ★★.

Let $\Phi_e$ be a functional such that $\Phi^X_e$ is total for every $X \in \cs$. Show that there is a computable function $b$ such that $\use^X_e(x) \leq b(x)$ for all $X$ and $x$.

Hint

Use König’s lemma, or the compactness of $\cs$: for a fixed $x$, consider the strings $\sigma$ on which the computation $\Phi^\sigma_e(x)$ does not yet converge.

Solution

First, for every string $\sigma$, the computation of the machine $e$ on input $x$ with oracle $\sigma$ either halts or reaches a cell $k \geq |\sigma|$ after finitely many steps. Otherwise it would run forever while reading only cells $k < |\sigma|$, and with any oracle $X \succ \sigma$ it would perform the same steps, so that $\Phi^X_e(x)\diverge$, contradicting the hypothesis. Hence the relation $\Phi^\sigma_e(x)\converge$ is decidable: run the computation until one of the two events occurs.

Fix $x$, and let $T_x$ be the set of strings $\sigma$ such that $\Phi^{\tau}_e(x)\diverge$ for every $\tau \preceq \sigma$. It is closed under prefixes and decidable. If $T_x$ contained strings of every length, then by König’s lemma (an infinite binary tree has an infinite path) there would be $X$ with all its prefixes in $T_x$, and then $\Phi^X_e(x)\diverge$ by Proposition 1.5, a contradiction. So there is a length $\ell$ such that no string of length $\ell$ belongs to $T_x$, and the least such $\ell$ is found by testing the $2^\ell$ strings of length $\ell = 0, 1, 2, \dots$ in turn. Let $b(x)$ be this $\ell$. Every $X$ has a prefix $\tau$ of length at most $b(x)$ with $\Phi^\tau_e(x)\converge$, and then $\use^X_e(x) \leq |\tau| \leq b(x)$ by the use principle.

1.7 Notes and references

Oracle machines were introduced by Turing in his Princeton thesis, published in 1939, in the study of ordinal logics. Post (1944, 1948) and Kleene and Post (1954) made relative computability the central notion of the theory. The model with an oracle tape follows Rogers’ and Soare’s textbooks; models with query states give the same notion of relative computability.

• A. M. Turing, Systems of logic based on ordinals, Proceedings of the London Mathematical Society (2) 45 (1939), 161–228.
• S. C. Kleene and E. L. Post, The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics 59 (1954), 379–407.
• T. Baker, J. Gill and R. Solovay, Relativizations of the P =? NP question, SIAM Journal on Computing 4 (1975), 431–442.
• R. I. Soare, Turing Computability: Theory and Applications, Springer, 2016.