Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo
“Stronger Notions of Randomness”
Last semester we studied Martin-Lof randomness, and the weaker notion of Schnorr ran- domness. We will now introduce 2-randomness and weak 2-randomness, which are stronger notions than Martin-Lof randomness.
We will investigate some of the properties of each of these classes, and separate the two classes by giving a real which is weakly 2-random but not 2-random. We will state a complexity characterisation of 2-randomness. The proof of this characterization will be completed in the next seminar.
MC 5403