Computability Learning Seminar

Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo

“Lowness Properties”

AbstractGiven a class C of real numbers which can be relativized to a class C(X) depending on a real parameter X, we say that X is low for C if C(X)=C.

We will consider several classes related to algorithmic randomness for which such a notion of lowness exists, including lowness for Martin-Lof randomness, for weak 2-randomness, and for prefix-free complexity K. We will investigate the properties of these notions of lowness, as well as the relationships between them.

MC 5403