Teachers, learners, and oracles. (English) Zbl 1529.03226

Beros, Achilles; de la Higuera, Colin

Notre Dame J. Formal Logic 60, No. 1, 13-26 (2019).

Summary: We exhibit a family of computably enumerable sets which can be learned within polynomial resource bounds given access only to a teacher but which requires exponential resources to be learned given access only to a membership oracle. In general, we compare the families that can be learned with and without teachers and oracles for four measures of efficient learning.

MSC:

03D80	Applications of computability and recursion theory
68Q32	Computational learning theory
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

learning theory; oracles; teachers; recursion theory