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 a homework assignment about the material in the first half of the course: while it does not count towards your grade, passing it is a necessary condition for passing the course. In the second half of the seminar, you are required to submit a question for discussion by the day prior to each lecture. A discussion question ideally comes in the form of indicating some aspect of the text you find problematic, implausible, and/or confusing; and a brief motivation why you think so. 
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  MartinLöf randomness.  Primary: Bienvenu, Shafer, & Shen (2009), sect. 7. Dasgupta (2011), sects. 2–3, 6.1.
Background: Nies (2009), sects. 3.1–3.2. MartinLöf (1966). 
Deadline assignment. 
Fri Jun 14  Schnorr's theorem: equivalence of different notions. The "MartinLöfChaitin thesis".  Primary: Dasgupta (2011), sects. 9, 11.1–11.3, 12. Bienvenu, Shafer, & Shen (2009), sects. 8, 10.
Background: Delahaye (1993). Schnorr (1977). Nies (2009), sects. 7.1–7.3. 

Fri Jun 21  NO CLASS.  
Fri Jun 28  The "MartinLöfChaitin thesis".  Porter (2016).  
Fri Jul 05  Randomness in science (1).  McAllister (2003).  
Fri Jul 12  Randomness in science (2).  Eagle (2005).  
Fri Jul 19  Randomness in psychology.  Vitányi & Chater (2017).  
Fri Jul 26  Chaitin's incompleteness theorem.  Raatikainen (1998).  
Mon Sep 23  Deadline term paper. 
Material
 Bienvenu, Shafer, & Shen (2009). On the history of martingales in the study of randomness. Elec. J. Hist. Prob. Stat. [link]
 Chaitin (1974). Informationtheoretic computation complexity. IEEE T. Inform. Theory. [link]
 Cooper (2003). Computability Theory. [link]
 Cover & Thomas (2006). Elements of Information Theory, second edition. [link]
 Dasgupta (2011). Mathematical foundations of randomness. Handbook of the Philosophy of Science: Philosophy of Statistics [link]
 Delahaye (1993). Randomness, unpredictability and absence of order: the identification by the theory of recursivity of the mathematical notion of random sequence. Philosophy of Probability. [link]
 Eagle (2005). Randomness is unpredictability. Brit. J. Philos. Sci. [link]
 Eagle (2010). Chance versus randomness. Stanford Encyclopedia of Philosophy. [link]
 Gillies (2000). Philosophical Theories of Probability. [link]
 Jeffrey (1977). Mises redux. Basic Problems in Methodology and Linguistics. [link]
 Van Lambalgen (1987). Von Mises' definition of random sequences reconsidered. J. Symb. Log. [link]
 Van Lambalgen (1989). Algorithmic information theory. J. Symb. Log. [link]
 Li & Vitányi (2008). An Introduction to Kolmogorov Complexity and Its Applications, third edition. [link]
 MartinLöf (1966). The definition of random sequences. Inform. Contr. [link]
 McAllister (2003). Algorithmic randomness in empirical data. Stud. Hist. Phil. Sc. [link]
 McAllister (2005). Algorithmic compression of empirical data: Reply to Twardy, Gardner, and Dowe. Stud. Hist. Phil. Sc. [link]
 Nies (2009). Computability and Randomness. [link]
 Osherson & Weinstein (2008). Recognizing strong random reals. Rev. Symb. Log. [link]
 Porter (2012). Mathematical and philosophical perspectives on algorithmic randomness. PhD thesis. [link]
 Porter (2014). Kolmogorov on the role of randomness in probability theory. Math. Struct. Comp. Sc. [link]
 Porter (2016). On analogues of the ChurchTuring thesis in algorithmic randomness. Rev. Symb. Log. [link]
 Raatikainen (1998). On interpreting Chaitin's incompleteness theorem. J. Phil. Log. [link]
 Raatikainen (2000). Algorithmic information theory and undecidability. Synthese. [link]
 Schnorr (1971). A unified approach to the definition of random sequences. Math. Syst. Theory. [link]
 Schnorr (1977). A survey of the theory of random sequences. Proceedings of the Fifth International Congress on Logic, Methodology and Philosophy of Science, Part III. [link]
 Shen, Uspensky, & Vereshchagin (2017). Kolmogorov Complexity and Algorithmic Randomness. [link]
 Smith (1998). Explaining chaos. [link]
 Soare (2016). Turing Computability: Theory and Applications. [link]
 Twardy, Gardner & Dowe (2005). Empirical data sets are algorithmically compressible: Reply to McAllister? Stud. Hist. Phil. Sc. [link]
 Vitányi & Chater (2017). Identification of probabilities. J. Math. Psych. [link]