Computability Learning Seminar

Wednesday, February 3, 2016 3:30 pm - 3:30 pm EST (GMT -05:00)

Jonathan Stephenson, Department of Pure Mathematics, University of Waterloo

“Bases for Randomness”

We often regard the computational power of a set A as being synonymous with the class of sets A is able to compute. However, we might instead ask which sets are able to compute A. The class of such sets is called the cone above A. When the cone above A consists of few sets, we may think of A as being difficult to compute. We wish to make the term ”few sets” precise.

We will see that if A is incomputable, the class of sets which can compute A is of measure zero, so regarding measure zero as a condition indicating a class contains ”few sets” does not allow us to make a significant distinction in terms of computational difficulty.

We will say that A is a base for ML-randomness if the cone above A contains a set which is ML-random relative to A. Those sets which are not bases for ML-randomness may be regarded as difficult to compute. This provides a better notion than measure zero, because any set which is low for ML-randomness is a base for ML-randomness, but that there are many sets which are not bases for ML-randomness.

MC 5403