Browsing by Author "KHOUSSAINOV, Bakhadyr"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Applications of Kolmogorov Complexity to Computable Model Theory
    (2006-09-07T06:46:20Z) KHOUSSAINOV, Bakhadyr; SEMUKHIN, Pavel; STEPHAN, Frank
    In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not countably categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity. With a variation of this construction, we also provide an example of a uncountably categorical but not countably categorical saturated Sigma-0-1-structure with a unique computable isomorphism type. In addition, using the construction we give an example of an uncountably categorical but not countably categorical theory whose only non-computable model is the prime one.
  • 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.