���������� �. �.
������ ��������������� ��������� ������� ���������� �������

����������� ��������������� ��������� ��������� �������� ������������ ������� ���������� �������: �������� ���������� ������� (∑₂⁰ -������), ���������� ������� � ω-������������� �������� (Δ_ω⁰ -������� ∏⁰ _ω+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)