Journal of Symbolic Logic · 2007 · 21 citations · 7 references
ComputingComputer ScienceMathematicsDiscrete MathematicsSet TheoryTheory Of ComputationComplexity TheoryComputability TheoryComputational ModelsModel TheoryStructural ComplexityComputable Model TheoryComputable Structure TheoryKolmogorov ComplexityPrime Models
Abstract In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ℵ 0 -categorical saturated structure with a unique computable isomor-phism 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 ℵ 1 -categorical but not ℵ 0 -categorical saturated -structure with a unique computable isomorphism type. In addition, using the construction we give an example of an ℵ 1 -categorical but not ℵ 0 -categorical theory whose only non-computable model is the prime one.
7
Recursively enumerable sets and degrees
Robert I. Soare · Bulletin of the American Mathematical Society · 1978 · 1.6K citations · Full text
Choice Reviews Online · 2003 · 708 citations
Michael Morley · Transactions of the American Mathematical Society · 1965 · 391 citations