z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom