Browsing by Author "FRANKLIN, Johanna N. Y."

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Relativizations of Randomness and Genericity Notions
    (2009-02-10) FRANKLIN, Johanna N. Y.; STEPHAN, Frank; YU, Liang
    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.
  • No Thumbnail Available
    Item
    Schnorr trivial sets and truth-table reducibility
    (2008-03-04) FRANKLIN, Johanna N. Y.; STEPHAN, Frank
    In this paper, we give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations enable us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey, Griffiths and LaForte.