Coordinates Fridays from 10 AM to noon in room 021 of Ludwigstrasse 31.
Lecturers Benedict Eastaugh and Tom Sterkenburg.
Course description

Intuitively, it is very implausible that a regular sequence HTHTHTHT... is generated by subsequent tosses of a fair coin. Intuitively, such a sequence must have been generated in some more regular way: otherwise it would look much more unpredictable, or much harder to describe. But can we actually give a precise characterization of such truly random sequences?

Algorithmic randomness is a currently very active branch of computability theory that revolves around the question how we can characterize random sequences, making essential use of the notion of effective computability. In this seminar, we will study the main philosophical and mathematical elements of this field, as well as applications to foundations of statistics and of physics.

Contents and material

See the below schedule for details. (This schedule is provisionary; depending on participants' interests, we might make some changes as the course progresses.)

The first half of the seminar, six lectures, is a crash course on the basic concepts and results of algorithmic randomness. Here we will rely on sections from the textbooks by Li & Vitányi (2008) and Nies (2009), and the overview articles by Dasgupta (2011) and Bienvenu, Shafer, & Shen (2009). We also make available optional background reading, both textbooks and articles, for those who wish to go deeper into certain topics.

In the second half of the seminar, five lectures, we will read a number of papers on specific philosophical themes and applications of algorithmic randomness.

Assessment

The course is worth 9 ECTS. Your grade will be determined by a term paper at the end of the course. In addition, there will be two homework assignments about the material in the first half of the course: while these do not count towards your grade, passing them is a necessary condition for passing the course.

Schedule

Date Topic Material Assignments
Fri Apr 26 Introduction. Overview of the course: the problem of randomness. Primary: Dasgupta (2011), sects. 1–2.
Fri May 03 Fundamentals of computability theory. Primary: Dasgupta (2011), sect. 4 (except 4.4).
Background: Soare (2016), ch. 1. Nies (2009), sects. 1.1–1.4. Li & Vitányi (2008), sects. 1.1–1.8.
Fri May 10 Kolmogorov complexity. Primary: Dasgupta (2011), sects. 7–8.
Background: Nies (2009), sects. 2.1–2.2. Li & Vitányi (2008), sects. 2.1–2.2, 3.1, 3.3.
Fri May 17 NO CLASS.
Fri May 24 From von Mises to Kolmogorov. Primary: Bienvenu, Shafer, & Shen (2009), sects. 1–6. Dasgupta (2011), sect. 5.
Background: Porter (2014). Gillies (2000), ch. 5. Van Lambalgen (1987).
Fri May 31 NO CLASS: Workshop on Computation in Scientific Theory and Practice.
Fri Jun 07 Martin-Löf randomness. Primary: Dasgupta (2011), sects. 3, 6. Bienvenu, Shafer, & Shen (2009), sect. 7. Nies (2009), sects. 3.1–3.2.
Background: Martin-Löf (1966).
Deadline assignment 1.
Fri Jun 14 Schnorr randomness. Schnorr's theorem: equivalence of different notions. Primary: Bienvenu, Shafer, & Shen (2009), sects. 8–10. Dasgupta (2011), sects. 11–12. Nies (2009), sects. 7.1–7.3.
Background: Schnorr (1977).
Fri Jun 21 NO CLASS.
Fri Jun 28 Chaitin's incompleteness theorem. Raatikainen (1998). Deadline assignment 2.
Fri Jul 05 Randomness in science (1). McAllister (2003).
Fri Jul 12 Randomness in science (2). Eagle (2005).
Fri Jul 19 Randomness and learning theory. Osherson & Weinstein (2008).
Fri Jul 26 The "Martin-Löf-Chaitin thesis". Porter (2016).
Mon Sep 23 Deadline term paper.

Material