Schnorr trivial reals: A construction

Abstract

A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null σ0 2 (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing reals that are K-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. Nies proved in (Adv Math 197(1):274-305, 2005) that all K-trivial reals are low. In this paper, we prove that if bf h'} ≥T bf 0', then h contains a Schnorr trivial real. Since this concept appears to separate computational complexity from computational strength, it suggests that Schnorr trivial reals should be considered in a structure other than the Turing degrees. © 2007 Springer-Verlag.