论文标题
可学习性和积极的等价关系
Learnability and Positive Equivalence Relations
论文作者
论文摘要
Gavryushkin，Khoussainov，Jain和Stephan的先前工作研究了在正面（循环枚举）等价关系给出的世界中，可以实现哪些代数结构，这些关系将自然数量分为无限的等效类别。本工作调查了无限的单一编号递归列举的（R.E.）家庭，并询问等价关系的选择在从积极的示例中研究极限的学习性时，如何影响这些类别的可学习性特性，也称为从文本中学习。对于这种正等价关系的所有选择，对于以下每个条目，都有一个编号的R.E.满足它的家庭：（a）他们的行为是正确学习的，但不能摇摇欲坠； （b）它们是可以学习的，但不能自信地学习； （c）它们在行为上不能正确地学习。此外，存在一个积极的等价关系，该关系强制执行（d）在这种等价关系下关闭的每个智慧学习的单一语言家族都已经可以解释了，并且无法自信地学习。
Prior work of Gavryushkin, Khoussainov, Jain and Stephan investigated what algebraic structures can be realised in worlds given by a positive (= recursively enumerable) equivalence relation which partitions the natural numbers into infinitely many equivalence classes. The present work investigates the infinite one-one numbered recursively enumerable (r.e.) families realised by such relations and asks how the choice of the equivalence relation impacts the learnability properties of these classes when studying learnability in the limit from positive examples, also known as learning from text. For all choices of such positive equivalence relations, for each of the following entries, there are one-one numbered r.e. families which satisfy it: (a) they are behaviourally correctly learnable but not vacillatorily learnable; (b) they are explanatorily learnable but not confidently learnable; (c) they are not behaviourally correctly learnable. Furthermore, there is a positive equivalence relation which enforces that (d) every vacillatorily learnable one-one numbered family of languages closed under this equivalence relation is already explanatorily learnable and cannot be confidently learnable.
