Midwest Computability Seminar

Part vii

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


Meeting ID: 997 5433 2165

Passcode: midwest

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

Randomness notions and reverse mathematics

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.