Relativizations of Randomness and Genericity Notions
| dc.contributor.author | FRANKLIN, Johanna N. Y. | en_US |
| dc.contributor.author | STEPHAN, Frank | en_US |
| dc.contributor.author | YU, Liang | en_US |
| dc.date.accessioned | 2009-03-17T01:37:49Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:13Z | |
| dc.date.available | 2009-03-17T01:37:49Z | en_US |
| dc.date.available | 2017-01-23T07:00:13Z | |
| dc.date.issued | 2009-02-10 | en_US |
| dc.description.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. | en_US |
| dc.format.extent | 187733 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/2899 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TRA2/09 | en_US |
| dc.title | Relativizations of Randomness and Genericity Notions | en_US |
| dc.type | Technical Report | en_US |