Learning paradigms classified by the arithmetical complexity of their learnable language families
Files
Publication date
Authors
DOI
Document Type
Bachelor Thesis
Metadata
Show full item recordCollections
License
CC-BY-NC-ND
Abstract
This thesis provides insight into the field of recursion theory, and more specifically, algorithmic learning theory (Gold, 1967). Gold has constructed an abstract model for language acquisition by (Turing) machines. In 2013, Beros has investigated the complexity of the class of languages learnable under Gold's model in terms of the arithmetical hierarchy, as well as the complexity of the classes of languages learnable under certain variations on that model. Beros' proofs are reconstructed and sometimes slightly corrected in this thesis. Furthermore, Beros' claim of the relation between the complexity of a class and the sophistication of the associated learning model is disputed.
Keywords
theoretical computer science, recursion theory, learning theory, algorithmic learning theory, arithmetical hierarchy, classification, completeness, Turing machine, language acquisition, explanatory learning, finite learning, behaviorally correct learning, anomalous learning, learning in the limit, decision problem, m-reducibility