Premium
Relativizations of randomness and genericity notions
Author(s) -
Franklin Johan. Y.,
Stephan Frank,
Yu Liang
Publication year - 2011
Publication title -
bulletin of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.396
H-Index - 48
eISSN - 1469-2120
pISSN - 0024-6093
DOI - 10.1112/blms/bdr007
Subject(s) - randomness , turing , base (topology) , mathematics , set (abstract data type) , discrete mathematics , computer science , statistics , mathematical analysis , programming language
A set A is a base for Schnorr randomness if it is Turing reducible to a set R that is Schnorr random relative to A , and the notion of a base for weak 1‐genericity can be defined similarly. We show that A is a base for Schnorr randomness if and only if A is a base for weak 1‐genericity if and only if the halting set K is not Turing reducible to A . Furthermore, we define a set A to be high for Schnorr randomness versus Martin‐Löf randomness if and only if every set that is Schnorr random relative to A is also Martin‐Löf random unrelativized, and we show that A is high for Schnorr randomness versus Martin‐Löf randomness if and only if K is Turing reducible to A . Results concerning highness for other pairs of randomness notions are also presented.