Geodesic
Complexity of Categorical Theories with Computable Models
Algebra i logika, Tome 43 (2004) no. 6, pp. 650-665

Voir la notice de l'article provenant de la source Math-Net.Ru

M. Lerman and J. Scmerl specified some sufficient conditions for computable models of countably categorical arithmetical theories to exist. More precisely, it was shown that if $T$ is a countably categorical arithmetical theory, and the set of its sentences beginning with an existential quantifier and having at most $n+1$ alternations of quantifiers is $\Sigma_{n+1}^0$ for any $n$, then $T$ has a computable model. J. Night improved this result by allowing certain uniformity and omitting the requirement that $T$ is arithmetical. However, all of the known examples of theories of $\aleph_0$-categorical computable models had low level of algorithmic complexity, and whether there are theories that would satisfy the above conditions for sufficiently large $n$ was unknown. This paper will include such examples.
Keywords: computable model, countably categorical theory. 
@article{AL_2004_43_6_a1,
     author = {S. S. Goncharov and B. Khoussainov},
     title = {Complexity of {Categorical} {Theories} with {Computable} {Models}},
     journal = {Algebra i logika},
     pages = {650--665},
     publisher = {mathdoc},
     volume = {43},
     number = {6},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2004_43_6_a1/}
}
TY  - JOUR
AU  - S. S. Goncharov
AU  - B. Khoussainov
TI  - Complexity of Categorical Theories with Computable Models
JO  - Algebra i logika
PY  - 2004
SP  - 650
EP  - 665
VL  - 43
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2004_43_6_a1/
LA  - ru
ID  - AL_2004_43_6_a1
ER  - 
%0 Journal Article
%A S. S. Goncharov
%A B. Khoussainov
%T Complexity of Categorical Theories with Computable Models
%J Algebra i logika
%D 2004
%P 650-665
%V 43
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2004_43_6_a1/
%G ru
%F AL_2004_43_6_a1
S. S. Goncharov; B. Khoussainov. Complexity of Categorical Theories with Computable Models. Algebra i logika, Tome 43 (2004) no. 6, pp. 650-665. http://geodesic.mathdoc.fr/item/AL_2004_43_6_a1/