Аннотация
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)).
Переведенное название | Оценка алгоритмической сложности классов вычислимых моделей |
---|---|
Язык оригинала | английский |
Страницы (с-по) | 512-523 |
Число страниц | 12 |
Журнал | Siberian Mathematical Journal |
Том | 49 |
Номер выпуска | 3 |
DOI | |
Состояние | Опубликовано - мая 2008 |