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