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, and produces an enumeration of A. See enumeration reducibility for a precise account.A set A is computably enumerable with oracle 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, 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 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 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.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 denote some computable pairing function. We build X as a set of elements where, such that for each, there is at least one pair in X. This ensures that B is computably enumerable with oracle 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 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, where x is the n-th element of X. If there is none yet, we choose y large enough such that the index is outside the current string X, and we add a 1 bit at this index. Doing this ensures that in the eventual value of X, there is some pair for each.
Second, let us call "admissible extension" an extension of the current X which respects the property that 1 bits are pairs. Denote by M the n-th oracle Turing machine. We use M to mean M associated to a specific oracle Z.
We distinguish three cases.
1. There is an admissible extension Y such that M 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 before enumerating x become in bounds, and we set X to this extended Y. This ensures that, however X is later extended, M 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, for any admissible extension Y. In this case, we do not change X; it is already ensured that eventually M 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, for Y admissible extension, are in A, and conversely, every element of A is enumerated by M for at least one admissible extension Y. In other words, A is exactly the set of all values enumerated by M 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 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.