Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo
“Martin-Lof Randomness and Solovay Tests”
We have seen that the Martin-Lof random real numbers are a reasonably natural notion: they are definable both in terms of Martin-Lof tests and in terms of complexity.
In this lecture, we will offer some evidence that Martin-Lof randomness is not just a natural notion, but also a robust one. We will see that to be Martin-Lof random, it suffices to have high complexity on an infinite computable set of initial segment lengths, and that Martin-Lof randomness is preserved by finite errors, computable sampling, and indeed even by computable permutation. We will note in passing that it is however not a notion that respects the structure of the Turing degrees.
We will also offer a third characterization of Martin-Lof randomness by using Solovay tests. This will allow us to give a stronger bound on the length of runs of zeros in a Martin-Lof random real.
MC 5403