Computability Learning Seminar

Wednesday, October 28, 2015 3:00 pm - 3:00 pm EDT (GMT -04:00)

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