LEARNING THEORY IN THE ARITHMETIC HIERARCHY
LEARNING THEORY IN THE ARITHMETIC HIERARCHY
复制标题
学习算术层次中的理论
DOI：
10.1017/jsl.2014.23
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Achilles A. Beros
中科院分区：
文献类型：
--
作者：
Achilles A. Beros
摘要我们考虑了在不同的学习标准下可学到的均匀计算的家庭索引集的算术复杂性。我们确定了这些集合的确切复杂性，这些集合对于有限学习的标准概念，以极限为单位的学习，行为正确的学习和极限上的异常学习。在证明$ {\ rm {\ sigma}} _ 5^0 $ -completeness在行为上正确学习的结果时，我们证明了独立利益的结果；如果一个统一的枚举家族是无法学习的，那么对于任何可计算的学习者，都有$ {\ rm {\ delta}} _ 2^0 $枚举见证失败。
Abstract We consider the arithmetic complexity of index sets of uniformly computably enumerable families learnable under different learning criteria. We determine the exact complexity of these sets for the standard notions of finite learning, learning in the limit, behaviorally correct learning and anomalous learning in the limit. In proving the ${\rm{\Sigma }}_5^0$-completeness result for behaviorally correct learning we prove a result of independent interest; if a uniformly computably enumerable family is not learnable, then for any computable learner there is a ${\rm{\Delta }}_2^0$ enumeration witnessing failure.