873 - Advanced Topics in Foundations

This course will cover some current active topics of research in computability theory and randomness. This is for graduate students who already know some basic computability theory and simple priority constructions. The two highlights of the course are:

1. Some recent topics in c.e. degrees: We will begin by reviewing some priority arguments - infinite injury and 0''' priority. We will talk about array computability and multiple permitting, and certain kinds of lattice embeddings. We will focus mainly on the low and high sets, and the different ways of classifying them. We will talk about traceability and its dual notions.

2. Effective randomness, with particular attention to lowness and highness properties. We will review basic randomness notions such as prefix-free complexity, effectively null sets and effective martingales. We will talk about triviality and various lowness notions, and their relationships with the Turing degrees. We will cover new combinatorial methods - the Decanter and Golden run proofs - introduced by Nies, Downey and Hirschfeldt. We also look at different kinds of effective forcing arguments in randomness, such as forcing with bushy trees, clumpy trees, and pi01 classes of positive measure.