Learning paradigms classified by the arithmetical complexity of their learnable language families

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.