6533b863fe1ef96bd12c783c
RESEARCH PRODUCT
On the relative sizes of learnable sets
Stuart A. KurtzCarl SmithFrank StephanLance FortnowWilliam GasarchMartin KummerRūsiņš Freivaldssubject
General Computer Science0102 computer and information sciencesMachine learningcomputer.software_genre01 natural sciencesMeasure (mathematics)Theoretical Computer ScienceTuring machinesymbols.namesake0101 mathematicsMathematicsBinary treeLearnabilitybusiness.industry010102 general mathematicsInductive inferenceCategoryInductive reasoningMeasureAbstract machine010201 computation theory & mathematicssymbolsArtificial intelligencebusinesscomputerComputer Science(all)description
Abstract 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 inferable sets become large rather quickly in the standard hierarchies of learnability. On the other hand, the complements of the learnable sets are all large.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1998-05-01 | Theoretical Computer Science |