zbMATH — the first resource for mathematics

On two problems of Turing complexity for strongly minimal theories. (English. Russian original) Zbl 1152.03023
Dokl. Math. 77, No. 3, 438-440 (2008); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 420, No. 5, 589-591 (2008).
From the text: One of the directions in computable model theory is connected to the study of the complexity of theories with computable models and to algorithmic complexity of other models of such theories. Let \(T\) be a consistent first-order theory. When can \(T\) be realized in a computable model? On the other hand, how complicated is it to build other models of the theory \(T\)? In other words, what is the Turing complexity of these models? These problems are connected to the fundamental question of existence of computable models with given model-theoretic and algorithmic properties, i.e., with a given specification. In the present paper, we study the algorithmic complexity of countable models of strongly minimal theories that are realized on computable models, as well as the algorithmic complexity of such theories.
03C57 Computable structure theory, computable model theory
03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI
[1] C. J. Ash and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Elsevier Sci., New York, 2000). · Zbl 0960.03001
[2] J. T. Baldwin and A. H. Lachlan, J. Symbolic Logic 36(1), 79–96 (1971). · Zbl 0217.30402
[3] S. A. Buechler, Essential Stability Theory (Springer-Verlag, Heidelberg, 1996). · Zbl 0864.03025
[4] H. Keisler and C. Chang, Model Theory (North-Holland, Amsterdam, 1973; Mir, Moscow, 1977).
[5] Y. L. Ershov and S. S. Goncharov, Constructive Models: Siberian School of Algebra and Logic (Consultants Bureau, New York, 2000).
[6] E. B. Fokina, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform. 5(2), 78–86 (2005).
[7] S. S. Goncharov, Mat. Zametki 23, 885–888 (1978).
[8] S. Goncharov, V. Harizanov, S. Lempp, et al., Proc. Am. Math. Soc. 131, 3901–3912 (2003). · Zbl 1035.03013
[9] S. S. Goncharov and B. M. Khusainov, Dokl. Math. 66, 52–54 (2002) [Dokl. Akad. Nauk 385, 299–301 (2002)].
[10] L. Harrington, J. Symbol. Logic 39, 305–309 (1974). · Zbl 0332.02055
[11] N. Khisamiev, Izv. Akad. Nauk KazSSR, Ser. Fiz.-Mat. 1, 83–84 (1974).
[12] K. Kudaibergenov, Sib. Mat. Zh. 21(5), 155–158 (1980).
[13] B. Khoussainov, A. Nies, and R. Shore, Notre Dame J. Formal Logic 38(2), 165–178 (1997). · Zbl 0891.03013
[14] B. Khoussainov, S. Lempp, M. Liskowski, and R. Solomon, Proc. Am. Math. Soc. 135, 3711–3721 (2007). · Zbl 1124.03016
[15] H. L. Rogers, Theory and Recursive Functions and Effective Computability (McGraw-Hill, New York, 1967; Mir, Moscow, 1972). · Zbl 0183.01401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.