DSpace at School of Computing, NUS: Item 1900.100/2899

Please use this identifier to cite or link to this item: http://hdl.handle.net/1900.100/2899

Title:	Relativizations of Randomness and Genericity Notions
Authors:	FRANKLIN, Johanna N. Y. STEPHAN, Frank YU, Liang
Issue Date:	10-Feb-2009
Series/Report no.:	;TRA2/09
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.
URI:	http://hdl.handle.net/1900.100/2899
Appears in Collections:	Technical Reports

Files in This Item:

File	Size	Format
TRA2-09.pdf	183Kb	Adobe PDF	View/Open