Computability and inductive learning
Course Description: In this course we will focus on the general problem of learnability understood as computational identifiability in the limit. What makes certain structures (computationally) learnable? Which properties of (computational) learners facilitate and which impair learning processes? In relation to those questions the following topics will be treated in the course: the variety of learning paradigms; short introduction to recursion theory for formal learning theory; abstract language learning: basic notions and definitions; Gold theorems; locking sequences and telltale subsets; Angluin’s theorem; restrictions of learned structures: uniformly recursive families of languages, uniformly recursively enumerable families of languages; restrictions on learners; consistent, conservative, and memory-limited learners; the restrictiveness of computable learning; mind-change complexity in identification in the limit; model-theoretic learning and its relationship with the numerical paradigm.
The overall goal of the course is to introduce the research field to students and young researchers, by presenting basic methods and techniques. We will foster the multidisciplinary perspective on the problem of learning and information dynamics, much needed in the context of the progressing specialization of the relevant disciplines. Moreover, the final part of the course will be devoted to two philosophical topics, whose logical analysis begs a computational learning theory-like approach: philosophy of science and iterated belief revision.