On the Classification of Computable LanguagesComputer Science & Information Technology Faculty Publications
Document TypeConference Proceeding
AbstractA one-sided classifier converges to 1 on every set inside a given class and outputs infinitely often a 0 on every set outside the class. A two-sided classifier converges in the first case to 1 and in the second to 0. This paper considers one-sided and two-sided classifiers dealing with computable sets as input. It provides theorems from which the classifiability of natural examples can be assessed and investigates the relations of the types of classification to inductive learning theory and structural complexity theory in terms of Turing degrees. Furthermore, it deals with the special cases of classification from positive data only and of inferring trial-and-error classifier programs.
Citation InformationCase, John et al. "On the Classification of Computable Languages." STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27 - March 1, 1997, Proceedings.