Randomness and Solovay degrees

Kenshi Miyabe, Andre Nies, Frank Stephan


We consider the behaviour of Schnorr randomness, a randomness notion weaker than Martin-Löf's,  for left-r.e. reals under Solovay reducibility.  Contrasting with results on Martin-Löf-randomenss, we show that Schnorr randomness is not upward closed in the Solovay degrees. Next, some left-r.e. Schnorr random α is the sum of two left-r.e. reals that are far from random.  We also show that the left-r.e. reals of effective dimension >r, for some rational r, form a filter in the Solovay degrees.

Full Text:

3. [PDF]

DOI: https://doi.org/10.4115/jla.2018.10.3

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Journal of Logic and Analysis ISSN:  1759-9008