Midlands Logic Seminar

TITLE

DATE

Study group: TBC

Invited speaker: Christopher Porter (Paris 7)
"Randomness, Probability, and Computation"

In this talk, I will discuss recent joint work with Laurent Bienvenu and Antoine Taveneaux on the limitations of probabilistic computation in the context of algorithmic randomness. More specifically, I will highlight our work on deep $\Pi^0_1$ classes, where a $\Pi^0_1$ class $P$ (i.e., an effectively closed subclass of $2^\omega$) is deep if it is maximally difficult to produce an initial segment of a member of $P$ via any probabilistic algorithm (understood as a Turing machine equipped with an algorithmically random oracle). As I will explain, the paradigm example of a deep class is the collection of consistent completions of Peano arithmetic (a result implicit in the work of Levin and Stephan). I will also outline some of the basic properties of deep $\Pi^0_1$ classes and will provide a number of other examples.