ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Sorting

Unknown

Relativizations of randomness and genericity notions (2011)

Franklin, J. N. Y., Stephan, F., Yu, L.

Oxford University Press

In: Bulletin of the London Mathematical Society

add to mindlist on the mindlist

Details

Publication Date: 2011-11-24

Description: 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.

Print ISSN: 0024-6093

Electronic ISSN: 1469-2120

Topics: Mathematics

Published by Oxford University Press

Permalink

	Location	Call Number	Expected	Availability

Others were also interested in ...

PAPER CURRENT

S·F·X

Fulltext

hit 1 - 1 | 1 hit