RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Algebra Logika: Year: Volume: Issue: Page: Find

 Algebra Logika, 2004, Volume 43, Number 6, Pages 650–665 (Mi al101)

Complexity of Categorical Theories with Computable Models

S. S. Goncharova, B. Khoussainovb

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b University of Auckland

Abstract: 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

Full text: PDF file (218 kB)
References: PDF file   HTML file

English version:
Algebra and Logic, 2004, 43:6, 365–373

Bibliographic databases:

UDC: 510.53+510.67
Revised: 16.09.2003

Citation: S. S. Goncharov, B. Khoussainov, “Complexity of Categorical Theories with Computable Models”, Algebra Logika, 43:6 (2004), 650–665; Algebra and Logic, 43:6 (2004), 365–373

Citation in format AMSBIB
\Bibitem{GonKho04} \by S.~S.~Goncharov, B.~Khoussainov \paper Complexity of Categorical Theories with Computable Models \jour Algebra Logika \yr 2004 \vol 43 \issue 6 \pages 650--665 \mathnet{http://mi.mathnet.ru/al101} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2135386} \zmath{https://zbmath.org/?q=an:1097.03027} \transl \jour Algebra and Logic \yr 2004 \vol 43 \issue 6 \pages 365--373 \crossref{https://doi.org/10.1023/B:ALLO.0000048826.92325.02} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-35148837362} 

• http://mi.mathnet.ru/eng/al101
• http://mi.mathnet.ru/eng/al/v43/i6/p650

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. A. N. Gavryushkin, “Complexity of Ehrenfeucht models”, Algebra and Logic, 45:5 (2006), 289–295
2. A. N. Gavryushkin, “Spectra of computable models for Ehrenfeucht theories”, Algebra and Logic, 46:3 (2007), 149–157
3. E. B. Fokina, “Index sets of decidable models”, Siberian Math. J., 48:5 (2007), 939–948
4. Khoussainov B.M., Laskowski M.C., Lempp S., Solomon R., “On the computability-theoretic complexity of trivial, strongly minimal models”, Proc. Amer. Math. Soc., 135:11 (2007), 3711–3721
5. Fokina E.B., “Index sets of computable structures with decidable theories”, Computation and Logic in the Real World, Proceedings, Lecture Notes in Computer Science, 4497, 2007, 290–296
6. Soskova A.A., “A jump inversion theorem for the degree spectra”, Computation and Logic in the Real World, Proceedings, Lecture Notes in Computer Science, 4497, 2007, 716–726
7. E. N. Pavlovskii, “Estimation of the algorithmic complexity of classes of computable models”, Siberian Math. J., 49:3 (2008), 512–523
8. S. S. Goncharov, “Algoritmicheskaya slozhnost schetnykh modelei silno minimalnykh teorii”, Vestn. NGU. Ser. matem., mekh., inform., 8:2 (2008), 38–53
9. Fokina E.B., “Index sets for some classes of structures”, Ann. Pure Appl. Logic, 157:2-3 (2009), 139–147
10. Soskova A., Soskov I.N., “A jump inversion theorem for the degree spectra”, J. Logic Comput., 19:1 (2009), 199–215
11. A. I. Stukachev, “Teorema ob obraschenii skachka dlya polureshetok $\Sigma$-stepenei”, Sib. elektron. matem. izv., 6 (2009), 182–190
12. Fokina E.B., Kalimullin I., Miller R., “Degrees of categoricity of computable structures”, Arch. Math. Logic, 49:1 (2010), 51–67
13. Khoussainov B., Montalban A., “A Computable N-0-Categorical Structure Whose Theory Computes True Arithmetic”, Journal of Symbolic Logic, 75:2 (2010), 728–740
14. Montalban A., “Rice Sequences of Relations”, Philos. Trans. R. Soc. A-Math. Phys. Eng. Sci., 370:1971, SI (2012), 3464–3487
15. S. S. Goncharov, M. I. Marchuk, “Index Sets of Autostable Relative to Strong Constructivizations Constructive Models”, J. Math. Sci., 205:3 (2015), 368–388
16. Fokina E.B. Harizanov V. Melnikov A., “Computable Model Theory”, Turing'S Legacy: Developments From Turing'S Ideas in Logic, Lecture Notes in Logic, 42, ed. Downey R., Cambridge Univ Press, 2014, 124–194
17. S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “The index set of Boolean algebras autostable relative to strong constructivizations”, Siberian Math. J., 56:3 (2015), 393–404
18. S. S. Goncharov, M. I. Marchuk, “Index sets of constructive models of bounded signature that are autostable relative to strong constructivizations”, Algebra and Logic, 54:2 (2015), 108–126
19. E. B. Fokina, S. S. Goncharov, V. Harizanov, O. V. Kudinov, D. Turetsky, “Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations”, Algebra and Logic, 54:4 (2015), 336–341
20. Soskova A.A. Soskova M.I., “Enumeration Reducibility and Computable Structure Theory”, Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60Th Birthday, Lecture Notes in Computer Science, 10010, ed. Day A. Fellows M. Greenberg N. Khoussainov B. Melnikov A. Rosamond F., Springer International Publishing Ag, 2017, 271–301
21. Andrews U., Knight J.F., “Strongly Minimal Theories With Recursive Models”, J. Eur. Math. Soc., 20:7 (2018), 1561–1594
•  Number of views: This page: 404 Full text: 103 References: 43 First page: 1