Learnability of Enumerable Classes of Recursive Functions from 'Typical' Examples

摘要

The paper investigates whether it is possible to learn every enumerable classes of recursive functions from "typical" examples. "Typical" means, there is a computable family of finite sets, such that for each function in the class there is one set of examples that can be used in any suitable hypothesis space for this class of functions. As it will turn out, there are enumerable classes of recursive functions that are not learnable from "typical" examples. The learnable classes are characterized.