Randomness and Solovay degrees

News
19 Mar 2018, online
5 Mar 2018, accepted by JLA

Title
Randomness and Solovay degrees
(with A. Nies and F. Stephan)

Type
Full paper

Journal
Journal of Logic and Analysis, Vol 10, pp.1–13, 2018.
Open access

Abstract
We consider the behaviour of Schnorr randomness, a randomness notion weaker than Martin-L\”of’s, for left-r.e. reals under Solovay reducibility. Contrasting with results on Martin-L\”of-randomenss, we show that Schnorr randomness is not upward closed in the Solovay degrees. Next, some left-r.e. Schnorr random $\alpha$ 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.

download
coromandel_JLA_final