Computability Learning Seminar

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