On one-sided versus two-sided classification (Q1407503)

A classifier is an algorithm that reads initial segments of the characteristic function of a set and, for each such segment, outputs \(1\) or \(0\). A class of sets \(A\) is one-sided (classifiable) if there exists a classifier that on the initial segments of \(A\) converges to \(1\) if and only if \(A\) is in the class. A class of sets \(A\) is two-sided (classifiable) if there exists a classifier that on the initial segments of \(A\) converges to \(1\) if \(A\) is in the class and to \(0\) if \(A\) is not in the class. These concepts play an important role in computational learning theory. The paper undertakes a detailed analysis of one-sided and two-sided classes. We list here several results: (1) there is a one-sided infinite class which has no infinite two-sided class; (2) there are one-sided classes which are not two-sided relative to any oracle; (3) (the Turing complexity of a class is by definition the set of all oracles which allow a two-sided classifier for the class) there is a one-sided class with a non-recursive degree. The paper investigates different notions of reductions and completeness for classes and also the effective measurability of one-sided and two-sided classes.