Selman's theorem

In computability theory, Selman's theorem is a theorem relating enumeration reducibility with enumerability relative to oracles. It is named after Alan Selman, who proved it as part of his PhD thesis in 1971.

Statement

Informally, a set A is enumeration-reducible to a set B if there is a Turing machine which receives an enumeration of B (it has a special instruction to get the next element, or none if it has not yet been provided), and produces an enumeration of A. See enumeration reducibility for a precise account.

A set A is computably enumerable with oracle B (or simply "in B") when there is a Turing machine with oracle B which enumerates the members of A; this is the relativized version of computable enumerability.

Selman's theorem: A set A is enumeration-reducible to a set B if and only if A is computably enumerable with an oracle X whenever B is computably enumerable with the same oracle X.

Discussion

Informally, the hypothesis means that whenever there is a program enumerating B using some source of information (the oracle), there is also a program enumerating A using the same source of information. A priori, the program enumerating A could be running the program enumerating B as a subprogram in order to produce the elements of A from those of B, but it could also be using the source of information directly, perhaps in a different way than the program enumerating B, and it could be difficult to deduce from the program enumerating B. However, the theorem asserts that, in fact, there exists a single program which produces an enumeration of A solely from an enumeration of B, without direct access to the source of information used to enumerate B.

From a slightly different point of view, the theorem is an automatic uniformity result. Let P be the set of total computable functions $f:\mathbb {N} \rightarrow \mathbb {N} \cup \{\bot \}$ such that the range of f with ⊥ removed equals A, and let Q be similarly defined for B. A possible reformulation of the theorem is that if P is Mučnik-reducible to Q, then it is also Medvedev-reducible to Q. . Informally: if every enumeration of B can be used to compute an enumeration of A, then there is a single (uniform) oracle Turing machine which computes some enumeration of A whenever it is given an enumeration of B as the oracle.

Proof

If A is enumeration-reducible to B and B is computably enumerable with oracle X, then A is computably enumerable with oracle X (it suffices to compose a machine that enumerates A given an enumeration of B with a machine that enumerates B with an oracle X).

Conversely, assume that A is not enumeration-reducible to B. We shall build X such that B is computably enumerable with oracle X, but A is not.

Let $\langle \bullet ,\bullet \rangle$ denote some computable pairing function. We build X as a set of elements $\langle x,y\rangle$ where $x\in B$, such that for each $x\in B$, there is at least one pair $\langle x,y\rangle$ in X. This ensures that B is computably enumerable with oracle X (through a semi-algorithm that takes an input x and searches for y such that $\langle x,y\rangle \in X$).

The construction of X is done by stages, following the priority method. It is convenient to view the eventual value of X as an infinite bit string (i-th bit is the boolean $i\in X$) which is constructed by incrementally appending to a finite bit string. Initially, X is the empty string.

We describe the n-th step of the construction. It extends X in two ways.

First, we ensure that X has a 1 bit at some index $\langle x,y\rangle$, where x is the n-th element of X. If there is none yet, we choose y large enough such that the index $\langle x,y\rangle$ is outside the current string X, and we add a 1 bit at this index (padding with 0 bits before it). Doing this ensures that in the eventual value of X, there is some pair $\langle x,y\rangle$ for each $x\in B$.

Second, let us call "admissible extension" an extension of the current X which respects the property that 1 bits are pairs $\langle x,y\rangle ,x\in B$. Denote by M the n-th oracle Turing machine. We use M(Z) to mean M associated to a specific oracle Z (if Z is a finite bit string, out of bounds requests return 0).

We distinguish three cases.

1. There is an admissible extension Y such that M(Y) enumerates some x that is not in A. Fix such an x. We further extend Y by padding it with 0s until all oracle queries that were used by M(Y) before enumerating x become in bounds, and we set X to this extended Y. This ensures that, however X is later extended, M(X) does not enumerate A, as it enumerates x which is not in A.

2. There is some value x in A which is not enumerated by any M(Y), for any admissible extension Y. In this case, we do not change X; it is already ensured that eventually M(X) will not enumerate A, because it cannot enumerate x — indeed, if it did, this would be done after a finite number of oracle invocations, which would lie in some admissible extension Y.

3. We show that the remaining case is absurd. Here, we know that all values enumerated by M(Y), for Y admissible extension, are in A, and conversely, every element of A is enumerated by M(Y) for at least one admissible extension Y. In other words, A is exactly the set of all values enumerated by M(Y) for an admissible extension Y. We can build a machine which receives an enumeration of B, uses it to enumerates admissible extensions Y, runs the M(Y) in parallel, and enumerates the values they yield. This machine is an enumeration reduction from A to B, which is absurd since we assumed no such reduction exists.

See also

• Enumeration reducibility
• Oracle machine
• Reduction (computability)