Relativizations of Randomness and Genericity Notions
No Thumbnail Available
Date
2009-02-10
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A set A is a basis for Schnorr randomness if and only if it is Turing reducible to a set R which is Schnorr random relative to A.One can define a basis for weak 1-genericity similarly. It is shown that A is a basis for Schnorr randomness if and only if A is a basis for weak 1-genericity if and only if the halting problem K is not Turing reducible to A. Furthermore, a set A is called high for Schnorr randomness versus Martin-Loef randomness if and only if every set which is Schnorr random relative to A is also Martin-Loef random unrelativized. It is shown that A is high for Schnorr randomness versus Martin-Loef randomness if and only if K is Turing reducible to A. Other results concerning highness for other pairs of randomness notions are also included.