Geodesic
Complexity of Categorical Theories with Computable Models
Algebra i logika, Tome 43 (2004) no. 6, pp. 650-665 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2004},
     volume = {43},
     number = {6},
     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
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
%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