Syllabus
Typicalness - measure theory, martingales
- Calibration of notion "sets of measure zero"
- Martin-Löf tests, Schnorr tests and their modifications
- Universal Martin-Löf test
- Basic properties of ML-random sets
- Relativization of Martin-Löf randomness, van Lambalgen theorem
- Martingales, randomness defined by various classes of martingales
Incompressibility - Kolmogorov complexity
- Plain and prefix-free Kolmogorov complexity
- Chaitin-randomness, equivalence of Martin-Löf randomness and Chaitin randomness
- Halting probability, Omega-number
- Algorithmic weakness, K-trivial sets
Annotation
Algorithmic randomness.
Concepts of Kolmogorov complexity, various variants. Algorithmic randomness based on measure theory. A connection to recursion theory.