Geodesic
Degree spectra of structures
Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University, Tome 158 (2018), pp. 23-39.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this survey, we discuss computability spectra of countable structures that provide a natural measure of noncomputability of a structure. This notion is a main tool of investigating algorithmic properties of countable structures. Along with a review of known results in this field, we present proofs of some new results to illustrate the method of interpretation which is a basic method of the field. We also discuss some remaining open questions.
Mots-clés : structure
Keywords: computable structure, spectrum of a structure, interpretation. 
@article{INTO_2018_158_a1,
     author = {I. Sh. Kalimullin and V. L. Selivanov and A. N. Frolov},
     title = {Degree spectra of structures},
     journal = {Itogi nauki i tehniki. Sovremenna\^a matematika i e\"e prilo\v{z}eni\^a. Temati\v{c}eskie obzory},
     pages = {23--39},
     publisher = {mathdoc},
     volume = {158},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/INTO_2018_158_a1/}
}
TY  - JOUR
AU  - I. Sh. Kalimullin
AU  - V. L. Selivanov
AU  - A. N. Frolov
TI  - Degree spectra of structures
JO  - Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
PY  - 2018
SP  - 23
EP  - 39
VL  - 158
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/INTO_2018_158_a1/
LA  - ru
ID  - INTO_2018_158_a1
ER  - 
%0 Journal Article
%A I. Sh. Kalimullin
%A V. L. Selivanov
%A A. N. Frolov
%T Degree spectra of structures
%J Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
%D 2018
%P 23-39
%V 158
%I mathdoc
%U http://geodesic.mathdoc.fr/item/INTO_2018_158_a1/
%G ru
%F INTO_2018_158_a1
I. Sh. Kalimullin; V. L. Selivanov; A. N. Frolov. Degree spectra of structures. Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University, Tome 158 (2018), pp. 23-39. http://geodesic.mathdoc.fr/item/INTO_2018_158_a1/

[1] Alaev P. E., Terber Dzh., Frolov A. N., “Vychislimost na lineinykh poryadkakh, obogaschennykh predikatami”, Algebra i logika, 48 (2009), 549–563 | Zbl

[2] Bazhenov N. A., Frolov A. N., Kalimullin I. Sh., Melnikov A. G., “Vychislimost distributivnykh reshetok”, Sib. mat. zh., 58 (2017), 1236–1251 | Zbl

[3] Barvais Dzh., Spravochnaya kniga po matematicheskoi logike. Ch. I. Teoriya modelei, Nauka, M., 1982

[4] Goncharov S. S., Schetnye bulevy algebry i razreshimost, Nauchnaya kniga, Novosibirsk, 1996 | MR

[5] Goncharov S. S., Ershov Yu. L., Konstruktivnye modeli, Nauchnaya kniga, Novosibirsk, 1999 | MR

[6] Goncharov S. S., Dzgoev V. D., “Avtoustoichivost modelei”, Algebra i logika, 19:1 (1980), 45–58 | MR | Zbl

[7] Ershov Yu. L., Problemy razreshimosti i konstruktivnye modeli, Nauka, M., 1980

[8] Ershov Yu. L., Lavrov I. A., Taimanov A. D., Taitslin M. A., “Elementarnye teorii”, Usp. mat. nauk, 20 (1965), 37–108 | MR | Zbl

[9] Zubkov M. V., “Dostatochnye usloviya suschestvovaniya $\mathbf{0}^{\prime}$-predelno monotonnykh funktsii dlya vychislimykh $\eta$-skhozhikh lineinykh poryadkov”, Sib. mat. zh., 58 (2017), 107–121 | Zbl

[10] Kalimullin I. Sh., “Spektry stepenei nekotorykh algebraicheskikh struktur”, Algebra i logika, 46 (2007), 729–744 | Zbl

[11] Kalimullin I. Sh., “Pochti vychislimo perechislimye semeistva mnozhestv”, Mat. sb., 199 (2008), 33–40 | DOI | Zbl

[12] Kalimullin I. Sh., Faizrakhmanov M. Kh., “O stepenyakh perechislenii schetnykh semeistv vekhnerovskogo tipa”, Itogi nauki tekhn. Sovr. Mat. prilozh. Tematich. obzory, 157 (2018), 59–69

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

[14] Kogabaev N. T., “Teoriya proektivnykh ploskostei polna otnositelno spektrov stepenei i effektivnykh razmernostei”, Algebra i logika, 54 (2015), 599–627 | MR | Zbl

[15] Korovina M. V., Kudinov O. V., “Spektr polya vychislimykh deistvitelnykh chisel”, Algebra i logika, 55 (2016), 738–759

[16] Mak-Koi Ch. F. D., “O $\Delta^0_3$-kategorichnosti dlya lineinykh poryadkov i bulevykh algebr”, Algebra i logika, 41:5 (2002), 531–552 | MR

[17] Maltsev A. I., “O rekursivnykh abelevykh gruppakh”, Dokl. AN SSSR, 146 (1962), 1009–1012 | Zbl

[18] Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972

[19] Selivanov V. L., “Ob algoritmicheskoi slozhnosti algebraicheskikh sistem”, Mat. zametki, 44:6 (1988), 823–832

[20] Frolov A. N., “$\Delta_2^0$-kopii lineinykh poryadkov”, Algebra i logika, 45:3 (2006), 354–370 | MR | Zbl

[21] Frolov A. N., “Lineinye poryadki nizkoi stepeni”, Sib. mat. zh., 51:5 (2010), 1147–1162 | MR | Zbl

[22] Frolov A. N., “Zametka o $\Delta_2^0$-spektrakh lineinykh poryadkov i spektrakh otnosheniya sosedstva na nikh”, Izv. vuzov. Mat., 57:11 (2013), 74–78 | Zbl

[23] Frolov A. N., “Effektivnaya kategorichnost vychislimykh lineinykh poryadkov”, Algebra i logika, 54:5 (2015), 638–642 | MR | Zbl

[24] Khisamiev N. G., “Kriterii konstruktiviziruemosti pryamoi summy tsiklicheskikh $p$-grupp”, Izv. AN Kaz SSR. Cer. fiz.-mat., 1981, no. 1, 51–55 | Zbl

[25] Alaev P. E., “Computably categorical Boolean algebras enriched by ideals and atoms”, Ann. Pure Appl. Logic, 163 (2012), 485–499 | DOI | MR | Zbl

[26] Andersen B., Kach A., Melnikov A., Solomon R., “Jump degrees of torsion-free abelian groups”, J. Symb. Logic, 77 (2012), 1067–1100 | DOI | MR | Zbl

[27] Andrews U., Cai M., Kalimullin I., Lempp S., Miller J., Montalbán A., “The complements of lower cones of degrees and the degree spectra of structures”, J. Symb. Logic, 81 (2016), 997–1006 | DOI | MR | Zbl

[28] Ash C. J., “Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees”, Trans. Am. Math. Soc., 298:2 (1986), 497–514 | DOI | MR | Zbl

[29] Ash C., Knight J., Manasse M., Slaman T., “Generic copies of countable structures”, Ann. Pure Appl. Logic, 42 (1989), 195–205 | DOI | MR | Zbl

[30] Bazhenov N. A., “Effective categoricity for distributive lattices and Heyting algebras”, Lobachevskii J. Math., 38:4 (2017), 600–614 | DOI | MR | Zbl

[31] Calvert W., Harizanov V., Shlapentokh A., “Turing degrees of isomorphism types of algebraic objects”, J. London Math. Soc., 75 (2017), 273–286 | DOI | MR

[32] Csima B. F., Kalimullin I. S., “Degree spectra and immunity properties”, Math. Log. Q., 56 (2010), 67–77 | DOI | MR | Zbl

[33] Greenberg N., Montalban A., Slaman T. A., “Relative to any non-hyperarithmetic set”, J. Math. Log., 13:1 (2013), 1250007 | DOI | MR | Zbl

[34] Downey R. G., “Computability theory and linear orderings”, Stud. Logic Found. Math., 139 (1998), 823–976 | DOI | MR | Zbl

[35] Downey R., Greenberg N., Miller J. S., “Generic Muchnik reducibility and presentations of fields”, Isr. J. Math., 216:1 (2016), 371–387 | DOI | MR | Zbl

[36] Downey R. G., Jockusch C. G., “Every low Boolean algebra is isomorphic to a recursive one”, Proc. Am. Math. Soc., 122 (1994), 871–880 | DOI | MR | Zbl

[37] Feiner L. J., “Hierarchies of Boolean algebras”, J. Symb. Logic, 35 (1970), 365–373 | DOI | MR

[38] Fokina E. B., Friedman S. D., “Equivalence relations on classes of computable structures”, Lect. Notes Comp. Sci., 5635 (2009), 198–207 | DOI | MR | Zbl

[39] Frolov A. N., “Low linear orderings”, J. Log. Comput., 22:4 (2012), 745–754 | DOI | MR | Zbl

[40] Frolov A., “Scattered linear orderings with no computable presentation”, Lobachevskii J. Math., 35 (2014), 19–22 | DOI | MR | Zbl

[41] Frolov A., Harizanov V., Kalimullin I., Kudinov O., Miller R., “Spectra of high$_n$ and non-low$_n$ degrees”, J. Log. Comput., 22:4 (2012), 755–777 | DOI | MR | Zbl

[42] Frolov A. N., Zubkov M. V., “Increasing $\eta$-representable degrees”, Math. Log. Q., 55 (2009), 633–636 | DOI | MR | Zbl

[43] Goncharov S., Harizanov V., Knight J., McCoy C., Miller R., Solomon R., “Enumerations in computable structure theory”, Ann. Pure Appl. Logic, 136 (2005), 219–246 | DOI | MR | Zbl

[44] Diamondstone D., Greenberg N., Turetsky D., “Natural large degree spectra”, Computability, 2 (2013), 1–8 | DOI | MR | Zbl

[45] Harrison-Trainor M., Melnikov A., Miller R., Montálban A., “Computable functors and effective interpretability”, J. Symb. Logic, 82:1 (2017), 77–97 | DOI | MR | Zbl

[46] Hirschfeldt D. R., Khoussainov B., Shore R. A., Slinko A. M., “Degree spectra and computable dimensions in algebraic structures”, Ann. Pure Appl. Logic, 115 (2002), 71–113 | DOI | MR | Zbl

[47] Jockusch C. G., “Degrees in which the recursive sets are uniformly recursive”, Can. J. Math., 24 (1972), 1092–1099 | DOI | MR | Zbl

[48] Jockusch C. G., Soare R. I., “Degrees of orderings not isomorphic to recursive linear orderings”, Ann. Pure Appl. Logic, 52 (1991), 39–61 | DOI | MR

[49] Kach A., Montalbán A., “Cuts of linear orders”, Order., 28 (2011), 593–600 | DOI | MR | Zbl

[50] Kalimullin I., Khoussainov B., Melnikov A., “Limitwise monotonic sequences and degree spectra of structures”, Proc. Am. Math. Soc., 141 (2013), 3275–3289 | DOI | MR | Zbl

[51] Khoussainov B., Nies A., Shore R., “Computable models of theories with few models”, Notre Dame J. Formal Logic, 38 (1997), 165–178 | DOI | MR | Zbl

[52] Knight J. F., “Degrees coded in jumps of orderings”, J. Symb. Logic, 51:4 (1986), 1034–1042 | DOI | MR | Zbl

[53] Knight J. F., Stob M., “Computable Boolean algebras”, J. Symb. Logic, 65:4 (2000), 1605–1623 | DOI | MR

[54] Kruskal J. B., “The theory of well-quasi-ordering: a frequently discovered concept”, J. Comb. Theory. Ser. A., 13 (1972), 297–305 | DOI | MR | Zbl

[55] McCoy C. F. D., “$\Delta^0_2$-Categoricity in Boolean algebras and linear orderings”, Ann. Pure Appl. Logic, 119 (2003), 85–120 | DOI | MR | Zbl

[56] Melnikov A., “Enumerations and completely decomposable torsion-free abelian groups”, Th. Comput. Syst., 45 (2009), 897–916 | DOI | MR | Zbl

[57] Melnikov A. G., “New degree spectra of abelian groups”, Notre Dame J. Formal Logic, 58:4 (2017), 507–525 | DOI | MR | Zbl

[58] Miller R., “The $\Delta^0_2$-spectrum of a linear order”, J. Symb. Logic, 66:2 (2001), 470–486 | DOI | MR | Zbl

[59] Miller R., Poonen B., Schoutens H., Shlapentokh A., “A computable functor from graphs to fields”, J. Symb. Logic, 83:1 (2018), 326–348 | DOI | MR | Zbl

[60] Montálban A., “Computability theoretic classifications for classes of structures”, Proc. Int. Congr. Math., August 13–21, 2014, Seoul, Korea, 2014, 79–101 | MR | Zbl

[61] Oates S., Jump degrees of groups, Ph.D. Thesis, Univ. Notre Dame, 1989 | MR

[62] Remmel J. B., “Recursively categorical linear orderings”, Proc. Am. Math. Soc., 83:2 (1981), 387–391 | DOI | MR | Zbl

[63] Richter L. J., “Degrees of structures”, J. Symb. Logic, 46:4 (1981), 723–731 | DOI | MR | Zbl

[64] Simpson S. G., “Degrees of unsolvability: a tutorial”, Proc. CiE-2015/ Lect. Notes Comp. Sci., 9136 (2015), 83–94, Springer-Verlag, Berlin | DOI | MR

[65] Slaman T. A., “Relative to any nonrecursive set”, Proc. Am. Math. Soc., 126:7 (1998), 2117–2122 | DOI | MR | Zbl

[66] Soare R. I., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987 | MR

[67] Tarski A., Mostowski A., Robinson J., Undecidable theories, North-Holland, Amsterdam, 1953 | MR | Zbl

[68] Thurber J. J., “Every low$_2$ Boolean algebras”, Proc. Am. Math. Soc., 123 (1995), 3859–3866 | MR | Zbl

[69] Turlington A., Computability of Heyting algebras and distributive lattices, Ph.D. Thesis, Univ. of Connecticut, 2010 | MR

[70] Wehner S., “Enumerations, countable structures and Turing degrees”, Proc. Am. Math. Soc., 126:7 (1998), 2131–2139 | DOI | MR | Zbl