Randomness for non-computable measures (Q2846975)

The theory of algorithmic randomness for computable measures on Cantor space is well-developed. However, if \(\mu\) is a noncomputable measure then it stands to reason that when designating an effective \(\mu\)-null set we should have access to \(\mu\). A complication arises when \(\mu\) does not have a Turing degree but merely a continuous degree. The authors show that two definitions for \(\mu\)-randomness -- using representations of the measure which have Turing degree, or using uniform ``integral'' tests -- are equivalent. We thus get a robust notion of \(\mu\)-randomness for all measures~\(\mu\), computable or not.NEWLINENEWLINEThis theory is then used to better understand Levin's ``neutral'' measure, a measure relative to which every sequence is random. The authors use Kakutani's fixed-point theorem to construct such a measure. They also conclude that every PA-complete Turing degree computes a neutral measure; this gives a quick proof of a result by \textit{J. Reimann} and \textit{T. A. Slaman} [``Measures and their random reals'', Preprint, \url{arXiv:0802.2705}], that a sequence is noncomputable if and only if it is random relative to a measure of which it is not an atom. In fact, the ideals of total degrees below the continuous degrees of neutral measures are precisely the countable Scott sets.NEWLINENEWLINEIn later work [Notre Dame J. Formal Logic 55, No. 1, 1--10 (2014; Zbl 1332.03010)], the first author and \textit{J. Reimann} further investigate relative randomness and obtain further results concerning PA degrees.