On one-sided versus two-sided classification

One-sided classifiers are computable devices which read the characteristic function of a set and output a sequence of guesses which converges to 1 iff the set on the input belongs to the gven class. Such a classifier istwo-sided if the sequence of its output in addition converges to 0 on setsnot belonging to the class. The present work obtains the below mentionedresults for one-sided classes (= Σ⁰ ₂ classes) with respect to four areas: Turing complexity, 1-reductions, index sets and measure. There are one-sided classes which are not two-sided. This can have two reasons: (1) the class has only high Turing complexity. Then there are some oracles which allow to construct noncomputale two-sided classifiers. (2) The class is difficult because of some topological constraints and then there are also no nonrecursive two-sided classifiers. For case (1), several results are obtainedto localize the Turing complexity of certain types of one-sided classes. The concepts of 1-reduction, 1-completeness and simple sets is transferred to one-sided classes: There are 1-complete classes and simple classes, but no class is at the same time 1-complete nd simple. The one-sided classes have a natural numbering. Most of the common index sets relative to this numbering have the high complexity Π¹ ₁: the index set of the class {0,1}^∞, the index set of the equality problem and the index set of all two-sided classes. On the other side the index set of the empty class has complexity Π⁰ ₂; Π⁰ ₂ and Σ⁰ ₂ are the least complexities any nontrivial index set can have. Lusin showed that any one-sided class is measurable. Concerning the effectiveness of this measure, it is shown that a one-sided class has recursive measure 0 if it has measure 0, but that thre are one-sided classes having measure 1 without having measure 1 effectively. The measure of a two-sided class can be computed in the limit. Received: 2 December 1999 / Revised version: 28 February 2000 / Published online: 15 June 2001