Browsing by Author "YU, Liang"

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
    Turing Degrees And The Ershov Hierarchy
    (2009-06-23T02:46:45Z) STEPHAN, Frank; YANG, Yue; YU, Liang
    An n-r.e. set can be defined as the symmetric difference of n recursively enumerable sets. The classes of these sets form a natural hierarchy which became a well-studied topic in recursion theory. In a series of ground-breaking papers, Ershov generalized this hierarchy to transfinite levels based on Kleene's notations of ordinals and this work lead to a fruitful study of these sets and their many-one and Turing degrees. The Ershov hierarchy is a natural measure of complexity of the sets below the halting problem. In this paper, we survey the early work by Ershov and others on this hierarchy and present the most fundamental results. We also provide some pointers to concurrent work in the field.