We evaluate algorithmic complexity of the class of computable models of bounded signature that have a strong constructivization and are autostable relative to strong constructivizations.
Similar content being viewed by others
References
S. S. Goncharov and J. F. Knight, “Computable structure and non-structure theorems,” Algebra and Logic, 41, No. 6, 351–373 (2002).
A. T. Nurtazin, “Computable classes and algebraic criteria for autostability,” Ph. D. Thesis, Institute of Mathematics and Mechanics, Alma-Ata (1974).
S. S. Goncharov and Yu. L. Ershov, Constructive Models, Sib. School Alg. Log. [in Russian], Nauch. Kniga, Novosibirsk (1996).
S. S. Goncharov, “The problem of the number of non-autoequivalent constructivizations,” Dokl. Akad. Nauk SSSR, 251, No. 2, 271–274 (1980).
S. S. Goncharov, “Computability and computable models,” in: Int. Math. Ser. (New York), 5, Springer, New York (2007), pp. 99–216.
E. B. Fokina, “Index sets of decidable models,” Sib. Math. J., 48, No. 5, 939–948 (2007).
E. N. Pavlovskii, “Estimation of the algorithmic complexity of classes of computable models,” Sib. Math. J., 49, No. 3, 512–523 (2008).
E. N. Pavlovskii, “Index sets of prime model,” Sib. El. Mat. Izv., 5, 200–210 (2008).
Yu. L. Ershov and E. A. Palyutin, Mathematical Logic [in Russian], 6th ed., Fizmatlit, Moscow (2011).
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967).
S. S. Goncharov and A. T. Nurtazin, “Constructive models of complete solvable theories,” Algebra and Logic, 12, No. 2, 67–77 (1973).
A. T. Nurtazin, “Strong and weak constructivizations and computable families,” Algebra and Logic, 13, No. 3, 177–184 (1974).
S. S. Goncharov, “Index sets of almost prime constructive models,” Vestnik NGU, Mat., Mekh., Inf., 13, No. 3, 38–52 (2013).
S. S. Goncharov and B. Khoussainov, “Complexity of categorical theories with computable models,” Algebra and Logic, 43, No. 6, 365–373 (2004).
S. S. Goncharov, Countable Boolean Algebras and Decidability, Sib. School Alg. Log. [in Russian], Nauch. Kniga, Novosibirsk (1996).
M. G. Peretyatkin, “Strongly constructive models and enumerations for the Boolean algebra of recursive sets,” Algebra and Logic, 10, No. 5, 332–345 (1971).
D. Marker, “Non Σ n axiomatizable almost strongly minimal theories,” J. Symb. Log., 54, No. 3, 921–927 (1989).
S. S. Goncharov and M. I. Marchuk, “Index sets of constructive models that are autostable under strong constructivizations,” Vestnik NGU, Mat., Mekh., Inf., 13, No. 4, 43–67 (2013).
Author information
Authors and Affiliations
Corresponding authors
Additional information
Supported by RFBR (project No. 14-01-00376) and by the Grants Council (under RF President) for State Aid of Leading Scientific Schools (grant NSh-860.2014.1).
Translated from Algebra i Logika, Vol. 54, No. 2, pp. 163–192,March-April, 2015.
Rights and permissions
About this article
Cite this article
Goncharov, S.S., Marchuk, M.I. Index Sets of Constructive Models of Bounded Signature that are Autostable Relative to Strong Constructivizations. Algebra Logic 54, 108–126 (2015). https://doi.org/10.1007/s10469-015-9331-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10469-015-9331-z