Midwest Computability Seminar

XXV
Part vii


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

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

Meeting ID: 997 5433 2165

Passcode: midwest


Slides    Panopto video    YouTube video


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


DATE: Tuesday, November 10th, 2020

TIME: 3:00 - 4:00 PM Central

SPEAKER: Paul Shafer - University of Leeds

TITLE: Randomness notions and reverse mathematics

ABSTRACT: There are many notions of algorithmic randomness in addition to classic Martin-Löf randomness, such as 2-randomness, weak 2-randomness, computable randomness, and Schnorr randomness. For each notion of randomness, we consider the statement "For every set Z, there is a set X that is random relative to Z" as a set-existence principle in second-order arithmetic, and we compare the strengths of these principles. We also show that a well-known characterization of 2-randomness in terms of incompressibility can be proved in RCA0, which is non-trivial because it requires avoiding the use of Σ02 bounding.

This work is joint with André Nies.



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.