Applications of Arithmetic Complexity and Priority Arguments in Algorithmic Learning Theory
Achilles A. Beros · 2013
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 Σ0 5-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 ∆ 0 2 enumeration witnessing failure. Using related techniques, we show that TxtFex ∗ ∗ = TxtFext ∗ ∗, thereby answering a question posed by Osherson, Stob and Weinstein in 1986. We prove this in a strong way by exhibiting a family in TxtFex ∗ 2 \\ TxtFext ∗ ∗.Acknowledgements ii It would be remiss of me not to acknowledge those who have helped reach this landmark in my professional life. First of all, I would like to thank my advisor, Steffen Lempp, for guiding me through the process, helping me find research problems and teaching me so much of what I know about computability theory. In addition, I would like to thank Leo