Martin-Löf randomness

Random sequences defined as those avoiding every effectively null class: the uniform measure on Cantor space and the measure of effective classes, Martin-Löf and Solovay tests, the universal test, the law of large numbers, the characterization of randomness by prefix-free complexity, the randomness of Ω, Sacks's theorem on upper cones, the Kučera–Gács theorem, and the diagonally non-computable functions computed by random sequences.

Contents

1. 1

   Measure on Cantor space

   The uniform measure on Cantor space; open classes generated by prefix-free sets; the measure of a Σ⁰₁ class is left-c.e. and that of a Π⁰₁ class right-c.e.; null classes; the Lebesgue density lemma.

   1. 1.1 The uniform measure
   2. 1.2 Open classes
   3. 1.3 The measure of effective classes
   4. 1.4 Null classes
   5. 1.5 Relative measure and density
   6. 1.6 Exercises
   7. 1.7 Notes and references
   35 min
2. 2

   Martin-Löf tests

   Martin-Löf tests and Martin-Löf random sequences; a universal test; random sequences form a conull Σ⁰₂ class, with low and computably dominated members; random sequences satisfy the law of large numbers; Solovay tests define the same notion.

   1. 2.1 Tests
   2. 2.2 A universal test
   3. 2.3 Consequences
   4. 2.4 The law of large numbers
   5. 2.5 Solovay tests
   6. 2.6 Exercises
   7. 2.7 Notes and references
   40 min
3. 3

   The Levin–Schnorr theorem

   A sequence is Martin-Löf random if and only if its initial segments are incompressible for prefix-free complexity; Chaitin's Ω is random; the ample excess lemma and Chaitin's characterization of randomness by the growth of K(X↾n) − n.

   1. 3.1 Randomness and incompressibility
   2. 3.2 The halting probability is random
   3. 3.3 The ample excess lemma
   4. 3.4 Exercises
   5. 3.5 Notes and references
   35 min
4. 4

   Randomness and Turing degrees

   Sacks's theorem that upper cones of non-computable sets are null; the Kučera–Gács theorem that every set is computable from a random sequence; random sequences compute DNC functions, and DNC degrees are characterized by complexity.

   1. 4.1 Upper cones are null
   2. 4.2 Every set is computable from a random sequence
   3. 4.3 Random sequences compute DNC functions
   4. 4.4 Exercises
   5. 4.5 Notes and references
   40 min