André Nies
(Auckland)
Randomness and Analysis: a tutorial
The tutorial addresses the interactions of randomness and analysis. Randomness notions given by algorithmic tests can clarify the effective content of theorems such as Lebesgue's that a nondecreasing function is differentiable at almost every real. On the other hand, the point of view of analysis can study randomness notions. This shows invariance of randomness under the choice of a basis for the real, and leads to a better understanding of separations, such as Martin-Löf randomness versus the weaker notion defined by failure of all computable martingales.
The plan of the tutorial is as follows.
- Lecture 1
- Background on randomness via algorithmic tests. Constructive approaches to analysis of Bishop and Demuth, which with hindsight were the first to connect randomness with analysis.
- Lectures 2 and 3
- Effective versions of Lebesgues's Theorems: results of Pathak, Simpson and Rojas; Brattka Miller and Nies; results on Lipschitz functions by Freer et al.
Extensions to higher dimensions by Galicki and Turetsky ; the polynomial time setting (Nies).
Similar investigations in ergodic theory: V'yugin 1997; recent work by Downey, Nandakumar and Nies.
- Lecture 4
- We discuss the setting where the given functions are merely effective in the sense of computable enumerability. Lebesgue's density theorem for effectively closed sets; differentiability of interval-c.e. functions. An application: the recent solution of the covering problem showing that every K-trivial is below an incomplete Martin-Löf random.