Please use this identifier to cite or link to this item: https://doi.org/10.2178/jsl/1191333855
Title: Applications of kolmogorov complexity to computable model theory
Authors: Khoussainov, B.
Semukhin, P.
Stephan, F. 
Issue Date: Sep-2007
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
URI: http://scholarbank.nus.edu.sg/handle/10635/102869
ISSN: 00224812
DOI: 10.2178/jsl/1191333855
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on May 22, 2018

Page view(s)

18
checked on May 11, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.