Browsing by Author "YANG, Yue"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Computable Categoricity and the Ershov Hierarchy
    (2007-08-31) KHOUSSAINOV, Bakhadyr; STEPHAN, Frank; YANG, Yue
    In this paper, the notions of F[alpha]-categorical and G[alpha]-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the alpha-th level of the Ershov hierarchy, respectively. Separations obtained by natural graphs which are the disjoint unions of countably many finite graphs. Furthermore, for size-bounded graphs, an easy criterion is given to say when it is computable-categorical and when it is only G[2]-categorical; in the latter case it is not F[alpha]-categorical for any recursive ordinal alpha.
  • 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.