### 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.

##### About the seminar

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.

##### Logistics

All meetings for Term 1 2013 will be Friday from 4:00-6:00 in room 310 of Watson Building (School of Mathematics) on the campus of the University of Birmingham.

campus map
google maps

To get to campus, take train from Birmingham New Street to the University stop (7 minutes).

##### Organizers:

Dr Richard Kaye

School of Mathematics

University of Birmingham

http://web.mat.bham.ac.uk/R.W.Kaye/

Dr Walter Dean

Department of Philosophy

University of Warwick

http://go.warwick.ac.uk/whdean