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 given class. Such a classifier is two- sided if the sequence of its output in addition converges to 0 on sets not belonging to the class. The present work obtains the below mentioned result s for one-sided classes (= Sigma (0)(2) 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 reas ons: (1) the class has only high Turing complexity. Then there are some ora cles which allow to construct noncomputable two-sided classifiers. (2) The class is difficult because of some topological constraints and then there a re also no nonrecursive two-sided classifiers. For case ( 1), several resul ts are obtained to localize the Turing complexity of certain types of one-s ided 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 and simple. The one-sided classes have a natural numbering. Most of the common index se ts relative to this numbering have the high complexity Pi vertical bar: the index set of the class {0, 1}(infinity), the index set of the equality pro blem and the index set of all two-sided classes. On the other side the inde x set of the empty class has complexity Pi (0)(2); Pi (0)(2) and Sigma (0)( 2) are the least complexities any nontrivial index set can have. Lusin showed that any one-sided class is measurable. Concerning the effecti veness of this measure, it is shown that a one-sided class has recursive me asure 0 if it has measure 0. but that there are one-sided classes having me asure 1 without having measure 1 effectively. The measure of a two-sided cl ass can be computed in the limit.