Enumeration reducibility

In computability theory, enumeration reducibility is a specific type of reducibility. Roughly speaking, A is enumeration-reducible to B if an enumeration of B can be algorithmically converted to an enumeration of A. In particular, if B is computably enumerable, then A also is.

Introduction

In one of the possible formalizations of the concept, a Turing reduction from A to B is a Turing machine augmented with a special instruction "query the oracle". This instruction takes an integer x and instantly returns whether x belongs to B. The oracle machine should compute A, possibly using this special capability to decide B. Informally, the existence of a Turing reduction from A to B means that if it is possible to decide B, then this can be used to decide A.
Enumeration reducibility is a variant whose informal explanation is, instead, that if it is possible to enumerate B, then this can be used to enumerate A. The reduction can be defined by a Turing machine with a special oracle query instruction which takes no parameter, and either returns a new element of B, or returns no output. The oracle supplies the elements of B in any order. It can possibly return no output for some queries before resuming the enumeration. The machine should similarly enumerate the members of A, in any order and at any pace. Repetitions in the enumerations of A and B may be permitted or not; the concept is equivalent in both cases. Although this could be made precise, the definition given below is more common since it is formally simpler.
Enumeration reducibility is a form of positive reducibility, in the sense that the oracle machine receives information about which elements are in B, but no information about which elements are not in B. Indeed, if an element has not been listed yet, the oracle machine cannot know whether it will be listed later, or never.
The concept of enumeration reducibility was first introduced by the results of John Myhill, which concluded that "a set is many-one complete if and only if it is recursively enumerable and its complement is productive". This result extends to enumeration reducibility as well. Enumeration reducibility was later formally codified by Rogers and his collaborator Richard M. Friedberg in Zeitschrift für mathematische Logik und Grundlagen der Mathematik in 1959.

Definition

Source:
Let be a standard numbering of finite subsets of, and let be a standard pairing function. A set is enumeration reducible to a set if there exists a computably enumerable set such that for all,
When A is enumeration reducible to B, we write. The relation is a preorder. Its associated equivalence relation is denoted by.

Properties

The supremum of sets and with respect to is given by the disjoint unionA is Turing reducible to B if and only if is enumeration reducible to, where the plus operator is defined as. Informally, this operator encodes the positive and negative information about A in a positive way. Likewise, A is computably enumerable with oracle B if and only if A is enumeration reducible to.
Furthermore, A is enumeration reducible to B if and only if, for all X such that B is computably enumerable with oracle X, it holds that A is also computably enumerable with oracle X. This is Selman's theorem.

Variants

Strong enumeration reducibilities

In addition to enumeration reducibility, there exist strong versions, the most important one being s-reducibility. S-reducibility states that a computably enumerable real set is s-reducible to another computably enumerable real set if is at least as difficult to be approximated as. This method shows similarity to e-reducibility in that it compares the elements of multiple sets. In addition, the structure of s-degrees have natural analogs in the enumeration degrees.
The reasoning for using s-reducibility is summarized by Omandaze and Sorbi as a result of positive reducibility models being unable to answer certain oracle questions because they inherently model computational situations where incomplete oracle information is available. This is in contrast from the well-studied Turing reducibility, in which information is captured in both negative and positive values. In addition, T-reducibility uses information that is provided immediately and without delay. A strong reducibility is utilized in order to prevent problems occurring when incomplete information is supplied.

Partial functions

E-reducibility can be defined for partial functions as well. Writing graph, etc., we can define for partial functions :
Kleene's recursion theorem introduces the notion of relative partial recursiveness, which, by means of systems of equations, can demonstrate equivalence through between graphs of partial functions. E-reducibility relates to relative partial recursiveness in the same way that T-reducibility relates to μ-recursiveness.