Applications of Kolmogorov complexity to computable model theory

Abstract

In this paper we answer the following well-known open question in computable model theory Does there exist a computable not No-categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity With it variation of this construction, we also provide an example of an aleph(1)-categorical but not aleph(0)-categorical saturated Sigma(0)(1)-structure with a unique computable isomorphism type. In addition, using the construction we give an example of an aleph(1)-categorical but not aleph(0)-categorical theory whose only non-computable model is the prime one.