Midwest Computability Seminar

XXVII
Part iv


The Midwest Computability Seminar is meeting remotely in the fall of 2021. The recurring Zoom link is:

https://notredame.zoom.us/j/99754332165?pwd=RytjK1RFZU5KWnZxZ3VFK0g4YTMyQT09

Meeting ID: 997 5433 2165

Passcode: midwest


Sarah Reitzes: slides    Panopto video    YouTube video

Diego Rojas: slides    Panopto video    YouTube video


This session will be held jointly with the Computability Theory and Applications Online Seminar.


DATE: Monday, October 25th, 2021

TIME: 3:30 - 4:30 PM Central Time


We will have two speakers:


SPEAKER: Sarah Reitzes - University of Chicago

TITLE: Comparing induction and bounding principles over RCA0 and RCA*0

ABSTRACT: In this talk, I will discuss joint work with Damir D. Dzhafarov and Denis R. Hirschfeldt, and more recent work following that line of research. Our work centers on the characterization of reductions between Π12 problems P and Q in terms of winning strategies in certain games. These characterizations were originally introduced by Hirschfeldt and Jockusch in [1]. 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. This allows us to develop the idea of Weihrauch and generalized Weihrauch reduction over some base theory. Here, we will focus on the base theory RCA0 and the weaker system RCA*0. In this talk, I will explore these notions of reduction among various principles, including bounding and induction principles. I will present a metatheorem that allows us to obtain many nonreductions between these principles.

[1] D. R. Hirschfeldt and C. G. Jockusch, Jr.: On notions of computability-theoretic reduction between Π12 principles. Journal of Mathematical Logic 16 (1650002), 59 pp. (2016)


SPEAKER: Diego Rojas - Iowa State University

TITLE: Effective convergence notions for measures on the real line

ABSTRACT: In classical measure theory, there are two primary convergence notions studied for sequences of measures: weak and vague convergence. In this talk, we discuss a framework to study the effective theory of weak and vague convergence of measures on the real line. For effective weak convergence, we give an effective version of a characterization theorem for weak convergence called the Portmanteau Theorem. We also discuss the relationship between effective weak convergence and the structure of the space of finite Borel measures on the real line as a computable metric space. In contrast to effective weak convergence, we give an example of an effectively vaguely convergent sequence of measures that has an incomputable limit. Nevertheless, we discuss the conditions for which the limit of an effectively vaguely convergent sequence is computable and the conditions for which effective weak and vague convergence of measures coincide. This talk will feature joint work with Timothy McNicholl.



Past and Future Sessions

Previous Seminars:

If you haven't been receiving the announcements and would like to be included in the list, send an email to drh@math.uchicago.edu.