Learning theory in the arithmetic hierarchy II
- PDF / 290,066 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 28 Downloads / 225 Views
Mathematical Logic
Learning theory in the arithmetic hierarchy II Achilles A. Beros1 · Konstantinos A. Beros2 · Daniel Flores1 · Umar Gaffar1 · David J. Webb1 · Soowhan Yoon1 Received: 10 April 2018 / Accepted: 20 July 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract The present work determines the arithmetic complexity of the index sets of u.c.e. families which are learnable according to various criteria of algorithmic learning. Specifically, we prove that the index set of codes for families that are TxtFexab learnable is 40 -complete and that the index set of TxtFex∗∗ -learnable and the index set of TxtFext∗∗ -learnable families are both 50 -complete. Keywords Algorithmic learning theory · Computability theory · Recursion theory Mathematics Subject Classification 03D15
1 Introduction At its heart, the goal of algorithmic learning theory is a formalization of the intuitive concept of learning. Specifically, algorithmic learning theory aims to formalize the process of extrapolation. As a rudimentary example of extrapolation, if one is given the finite sequence 2, 4, 6, 8 a natural conclusion is that the sequence represents an initial segment of the infinite sequence of all even numbers. The process of extrapolating a generative algorithm
B
Achilles A. Beros [email protected] Konstantinos A. Beros [email protected]
1
Department of Mathematics, University of Hawaii at Manoa, 2565 McCarthy Mall, Keller Hall 401A, Honolulu, HI 96822, USA
2
Department of Mathematics, Miami University, 123 Bachelor Hall, 301 S. Patterson Ave., Oxford, OH 45056, USA
123
A. A. Beros et al.
from given finite data is modeled in a number of different ways in algorithmic learning theory. The standard model of learning – introduced in Gold [8] – is explanatory learning or EX-learning. A computable function M : 2
Data Loading...
