Sarah Reitzes (University of Chicago)

June 23, 2020 @ 10:00 am – 11:00 am

Title: Reduction games, provability, and compactness
by Sarah Reitzes (University of Chicago) as part of Computability theory and applications

In this talk, I will discuss joint work with Damir D. Dzhafarov and Denis R. Hirschfeldt. Our work centers on the characterization of problems P and Q such that P is omega-reducible to Q, as well as problems
P and Q such that RCA_0 proves Q implies P, in terms of winning strategies in certain games. These characterizations were originally introduced by Hirschfeldt and Jockusch. I will discuss extensions and generalizations of these characterizations, including
a certain notion of compactness that allows us, for strategies satisfying particular conditions, to bound the number of moves it takes to win. This bound is independent of the instance of the problem P being considered.