We are thrilled to extend a warm welcome to Davide Trotta, a postdoctoral researcher at the Department of Computer Science at the University of Pisa in Italy. Davide brings his knowledge and expertise to our community, and we are excited to have him as a guest speaker in our upcoming seminar series, which will take place on Monday, 4 December in our Theory Lab.
Title: Categorifying computable reducibilities
Abstract: One of the most relevant notions of categorical logic which enabled the study of logic from a purely algebraic perspective is the notion of a (hyper)doctrine, introduced in a series of seminal papers by F.W. Lawvere to synthesize the structural properties of logical systems. In this talk, I will introduce this categorical approach to logic and explain how various notions well-known in computability can be framed within this categorical framework.
In particular, I will present categorical formulations in terms of Lawvere doctrines for the Medvedev, Muchnik, and Weihrauch reducibilities.
Finally, I will discuss some universal properties of such doctrines, showing how this study enables us to identify, from an abstract perspective, the common features of these notions of reducibility.
This talk is based on joint work with Manlio Valenti and Valeria de Paiva.
