University Seminar- Computability, Complexity, and Algebraic Structure: Procrastination in Computability and Learning Theory

Time: Wednesday, April 1, 2:20–3:35 pm

Place: 1776 G Street, Room C-110

Speaker:  Keshav Srinivasan, Yeshiva University

Title: Procrastination in Computability and Learning Theory

Abstract: Identification in the limit is an abstract model of learning, with applications to both the psychology of how humans learn and to the theory of machine learning.  We will discuss work by Freivald and Smith concerning how procrastinating the forming of conclusions can increase the power of a learner.  We will also discuss work by Smith, Ambianis and others about enhancing this power further by counting down from computable ordinals and pseudo-ordinals to procrastinate even more.  In the final part of the talk, we will connect this work to the Ershov hierarchy, a computability-theoretic hierarchy indexed by computable ordinals and pseudo-ordinals.