Limits and Structure of Learnability and Provability

I will describe my two main areas of research: Learning in the Limit and Reverse Mathematics. Learning in the limit is one of the main computational models of learnability. A learner is modeled by a computational device which inductively generates hypotheses about an input language and stabilizes in the limit on a correct guess. Contrary to other models of learning, this model allows to decide questions of the following type: Is it the case that some learning constraint or learning strategy is necessary for learning some language class? I will discuss the case of so-called "U-shaped learning", a prominent and as-of-yet not well-understood feature of human learning in many contexts. The study of the effective (or computable) content and relative strength of theorems is one of the main areas of recent research in Computable Mathematics and Reverse Mathematics. I will outline a framework in which the following questions can be addressed: Given two theorems, is one stronger than the other or are they equivalent? Is it the case that one theorem is reducible to the other by a computable reduction? Given a problem, what is the complexity of its solutions to computable instances? I will discuss the case of Hindman's Finite Sums Theorem, which is the subject of a number of long-standing open problems in the area.


Time: 10:00
Duration: about 20 minutes
Venue: Dipartimento di Informatica, Via Salaria 113, Third Floor, Seminari Lecture Room
Speaker: Lorenzo Carlucci

© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma