We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models (Sigma(0)(2)-complete), computable models with omega-categorical theories (Delta(0)(omega)-complex Pi(0)(omega+2)-set), prime models (Delta(0)(omega)-complex Pi(0)(omega+2)-set), models with omega(1)-categorical theories (Delta(0)(omega)-complex Sigma(0)(omega+1)-set). We obtain a universal lower bound for the model-theoretic properties preserved by Marker's extensions (Delta(0)(omega)).

Translated title of the contributionОценка алгоритмической сложности классов вычислимых моделей
Original languageEnglish
Pages (from-to)512-523
Number of pages12
JournalSiberian Mathematical Journal
Issue number3
Publication statusPublished - May 2008


  • computable model
  • index set


Dive into the research topics of 'Estimation of the algorithmic complexity of classes of computable models'. Together they form a unique fingerprint.

Cite this