ON THE RELATIVE SIZES OF LEARNABLE SETS

Measure and category (or rather, their recursion-theoretical counterpa rts) have been used in theoretical computer science to make precise th e intuitive notion ''for most of the recursive sets'', We use the noti ons of effective measure and category to discuss the relative sizes of inferrible sets, and their complements. We find that inferable sets b ecome large rather quickly in the standard hierarchies of learnability . On the other hand, the complements of the learnable sets are all lar ge. (C) 1998-Elsevier Science B.V. All rights reserved.