Notions of randomness

Randomness notions around Martin-Löf randomness: randomness relative to an oracle and van Lambalgen's theorem, 2-randomness, weak 2-randomness and the theorem of Downey, Nies, Weber and Yu, and the weaker notions of Schnorr and Kurtz, which collapse onto Martin-Löf randomness in computably dominated degrees.

Contents

1. 1

   Relative randomness and van Lambalgen's theorem

   Martin-Löf randomness relative to an oracle; van Lambalgen's theorem that a join is random exactly when its halves are random, the second relative to the first; consequences for the Turing degrees of random sequences; 2-randomness.

   1. 1.1 Relative randomness
   2. 1.2 Van Lambalgen's theorem
   3. 1.3 2-randomness
   4. 1.4 Exercises
   5. 1.5 Notes and references
   35 min
2. 2

   Weak 2-randomness

   Sequences avoiding every null Π⁰₂ class; 2-randomness implies weak 2-randomness, which implies Martin-Löf randomness, both strictly; no universal test; the theorem of Downey, Nies, Weber and Yu that a random sequence is weakly 2-random exactly when it computes no non-computable c.e. set.

   1. 2.1 Definition and position
   2. 2.2 The Downey–Nies–Weber–Yu theorem
   3. 2.3 Exercises
   4. 2.4 Notes and references
   30 min
3. 3

   Schnorr and Kurtz randomness

   Kurtz randomness, avoiding null Π⁰₁ classes, and Schnorr randomness, passing Martin-Löf tests of computable measure; the implications between the notions; weakly 1-generic sets are Kurtz random but not Schnorr random; in computably dominated degrees, Kurtz randomness implies Martin-Löf randomness.

   1. 3.1 Definitions
   2. 3.2 Collapse in computably dominated degrees
   3. 3.3 Exercises
   4. 3.4 Notes and references
   30 min