Applications of Kolmogorov Complexity to Computable Model Theory

Journal of Symbolic Logic 72 (3):1041 - 1054 (2007)
  Copy   BIBTEX

Abstract

In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ‮א‬₀-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 ‮א‬₁-categorical but not ‮א‬₀-categorical saturated $\Sigma _{1}^{0}$ -structure with a unique computable isomorphism type. In addition, using the construction we give an example of an ‮א‬₁-categorical but not ‮א‬₁-categorical theory whose only non-computable model is the prime one

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,221

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Kolmogorov complexity for possibly infinite computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Every 2-random real is Kolmogorov random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Computable structures and the hyperarithmetical hierarchy.C. J. Ash - 2000 - New York: Elsevier. Edited by J. Knight.
Computability & unsolvability.Martin Davis - 1958 - New York: Dover Publications.
Tailoring recursion for complexity.Erich Grädel & Yuri Gurevich - 1995 - Journal of Symbolic Logic 60 (3):952-969.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Uncomputably Noisy Ergodic Limits.Jeremy Avigad - 2012 - Notre Dame Journal of Formal Logic 53 (3):347-350.

Analytics

Added to PP
2010-08-24

Downloads
14 (#842,546)

6 months
1 (#1,027,696)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations