Please use this identifier to cite or link to this item:
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.
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
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.


checked on Dec 11, 2018

Page view(s)

checked on Oct 12, 2018

Google ScholarTM



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