Павловский Е. Н.
Оценка алгоритмической сложности классов вычислимых моделей

Оценивается алгоритмическая сложность индексных множеств естественных классов вычислимых моделей: конечных вычислимых моделей (∑₂⁰ -полное), вычислимых моделей с ω-категоричными теориями (Δ_ω⁰ -сложное ∏⁰ _ω+2-множество), простых моделей (Δ_ω⁰-сложное ∏⁰ _ω+2-множество), моделей с ω₁-категоричными теориями (Δ_ω⁰-сложное ∑⁰ _ω+1-множество). Получена универсальная нижняя оценка для теоретико-модельных свойств, сохраняющихся при маркеровских расширениях (Δ_ω⁰).

Pavlovskii E. N.
Estimation of the algorithmic complexity of classes of computable models

We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models (∑₂⁰ -complete), computable models with ω-categorical theories (Δ_ω⁰ -complex ∏⁰ _ω+2 -set), prime models (Δ_ω⁰ -complex ∏⁰ _ω+2 -set), models with ω₁-categorical theories (Δ_ω⁰ -complex ∑⁰ _ω+1 -set. We obtain a universal lower bound for the model-theoretic properties preserved by Marker’s extensions (Δ_ω⁰).

Полный текст статьи / Full texts:

• PDF file (570 KB)
• PostScript file (1 MB)