Please use this identifier to cite or link to this item:
|Title:||Applications of kolmogorov complexity to computable model theory|
|Citation:||Khoussainov, B., Semukhin, P., Stephan, F. (2007-09). Applications of kolmogorov complexity to computable model theory. Journal of Symbolic Logic 72 (3) : 1041-1054. ScholarBank@NUS Repository. https://doi.org/10.2178/jsl/1191333855|
|Abstract:||In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not N0- 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 an N 1 -categorical but not N0-categorical saturated Σ1 0-structure with a unique computable isomorphism type. In addition, using the construction we give an example of an N 1-categorical but not N0-categorical theory whose only non-computable model is the prime one. © 2007, Association for Symbolic Logic.|
|Source Title:||Journal of Symbolic Logic|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Sep 17, 2018
checked on Aug 17, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.