6533b7d2fe1ef96bd125e9c4

RESEARCH PRODUCT

Measure, category and learning theory

Carl SmithWilliam GasarchLance FortnowRusins FreivaldsMartin KummerStuart A. KurtzFrank Stephan

subject

Preference learningRecursionTheoretical computer scienceLearnabilitySample exclusion dimensionComputer scienceConcept learningAlgorithmic learning theoryMeasure (mathematics)Recursive tree

description

Measure and category (or rather, their recursion theoretical counterparts) have been used in Theoretical Computer Science to make precise the intuitive notion “for most of the recursive sets.” We use the notions of effective measure and category to discuss the relative sizes of inferrible sets, and their complements. We find that inferrible sets become large rather quickly in the standard hierarchies of learnability. On the other hand, the complements of the learnable sets are all large.

https://doi.org/10.1007/3-540-60084-1_105