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/

[1] S. Goncharov, B. Khusainov, “Slozhnost kategorichnykh teorii s vychislimymi modelyami”, Dokl. AN, 385:3 (2002), 299–301 | MR | Zbl

[2] J. Baldwin, A. Lachlan, “On strongly minimal sets”, J. Symb. Log., 36:1 (1971), 79–96 | DOI | MR | Zbl

[3] L. Harrington, “Recursively presentable prime models”, J. Symb. Log., 39:2 (1974), 305–309 | DOI | MR | Zbl

[4] N. Khisamiev, “Silno konstruktivnye modeli razreshimykh teorii”, Izv. AN Kaz. SSR, cer. fiz.-mat., 1 (1974), 83–84 | Zbl

[5] S. S. Goncharov, “Konstruktivnye modeli $\omega_1$-kategorichnykh teorii”, Matem. zam., 23:6 (1978), 885–888 | MR | Zbl

[6] K. Kudaibergenov, “O konstruktivnykh modelyakh nerazreshimykh teorii”, Sib. matem. zh., 21:5 (1980), 155–158 | MR | Zbl

[7] B. Khoussainov, A. Nies, R. Shore, “On recursive models of theories”, Notre Dame J. Form. Log., 38:2 (1997), 165–178 | DOI | MR | Zbl

[8] S. Goncharov, B. Khusainov, “O slozhnosti teorii vychislimykh $\aleph_1$-kategorichnykh modelei”, Vestnik NGU, ser. matem., mekh. inform., 1:2 (2001), 63–76 | Zbl

[9] M. Lerman, J. Scmerl, “Theories with recursive models”, J. Symb. Log., 44:1 (1979), 59–76 | DOI | MR | Zbl

[10] J. Knight, “Nonarithmetical $\aleph_0$-categorical theories with recursive models”, J. Symb. Log., 59:1 (1994), 106–112 | DOI | MR | Zbl

[11] W. Hodges, A shorter model theory, Cambridge Univ. Press, Cambridge, 1997 | MR

[12] D. Marker, “Non-$\Sigma_n$-axiomatizable almost strongly minimal theories”, J. Symb. Log., 54:3 (1989), 921–927 | DOI | MR | Zbl

[13] G. Keisler, Ch. Ch. Chen, Teoriya modelei, Mir, M., 1977 | MR

[14] R. I. Soare, Recursively enumerable sets and degrees, Springer-Verlag, New York, 1987 | MR

[15] M. G. Peretyatkin, “O polnykh teoriyakh s konechnym chislom schetnykh modelei”, Algebra i logika, 12:5 (1973), 550–576