| dbo:abstract
|
- In computability theory and computational complexity theory, enumeration reducibility is a method of reduction that determines if there is some effective procedure for determining enumerability between sets of natural numbers. An enumeration in the context of e-reducibility is a listing of the elements in a particular set, or collection of items, though not necessarily ordered or complete. E-reducibility is a form of positive reducibility, meaning that only positive information is processed. Positive information denotes the logic syntax for "and" and "or". The syntax for negation, "not" is not included or used. According to Hartley Rogers Jr., an intuitive model that can be used to explain e-reducibility is as follows: Let sets and be given. Consider a procedure that is determined by a finite set of instructions in the following way. A computation is begun. The computation proceeds algorithmically except that, from time to time, the computing agent may be requested to obtain an “input" integer, and, from time to time the procedure yields an “output” integer. When an input is requested, any integer, or no integer, may be supplied. Assume that when the members of are supplied, in any order whatsoever as inputs, then the computation always eventually yields the set , in some order, as outputs. The order in which the members of appear may vary as the order of inputs varies. (We permit repetitions in the listing of and in the listing of .) If such a procedure exists we say that is enumeration reducible to . The concept of e-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 e-reducibility as well. E-reducibility was later formally codified by Rogers and his collaborator Richard M. Friedberg in Zeitschrift für mathematische Logik und Grundlagen der Mathematik (the predecessor of ) in 1959. (en)
|
