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	Martin-Löf randomness.	Primary: Bienvenu, Shafer, & Shen (2009), sect. 7. Dasgupta (2011), sects. 2–3, 6.1. Background: Nies (2009), sects. 3.1–3.2. Martin-Löf (1966).	Deadline assignment.
Fri Jun 14	Schnorr's theorem: equivalence of different notions. The "Martin-Löf-Chaitin 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 "Martin-Löf-Chaitin 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). Information-theoretic 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]
• Martin-Lö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 Church-Turing 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]