1 0 Ju l 2 00 8 Statistical Learning of Arbitrary Computable Classifiers

This work shows that learning over the set of all computable labeling functions is indeed possible, and develops a learning algorithm, but shows that bounding sample complexity independently of the distribution is impossible.