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.
The Midlands Logic Seminar was founded in 2011 and aims to cover all areas of mathematical logic, as well as related areas of theoretical computer science, and philosophy of mathematics. We typically have a study group session from 4:00-5:00 (term 1 topic: satisfcation classes) and a research talk from 5:00-6:00.
Dr Walter Dean
Department of Philosophy
University of Warwick