Old notes are available at the the 2010 website. In the present offering, we will replace the second half of the course with the following topics, which are active areas of research:

- Short lists containing short programs in short time!, a recent work by Shen, Zimand et. al. from 2013, a connection between extractors and Kolmogorov Complexity, which (in my view) is the most fundamental result about Kolmogorov Complexity in about 40 years.
- Normal
Numbers, which can be viewed as a very weak notion of
randomness. Fundamental open questions are whether well-known
transcendentals like π, e, etc. are normal, and whether there is
any algebraic irrational which is normal.
In the course, we show the following results - Pillai's equivalent characterization of normality using simple normality, the equivalence between finite-state incompressibility and normality, and the proof that a Champernowne-like sequence is finite-state incompressible, hence normal. (This utilizes a combinatorial insight inherent in Lempel and Ziv's 1978 paper on universal compression, and has not appeared explicitly anywhere.) [Notes]

- Homework 1, due March 1

- Kolmogorov,
A. N.
*Foundations of Probability Theory*, Chelsea, 1956 (original published in German as*Grundbegriffe der Wahrscheinlichkeitsrechnung*in 1933).