Turing computability: structural theory

M. M. Arslanov ; M. M. Yamaleev

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 157 (2018), pp. 8-41.

Résumé

In this work, we review results of the last years related to the development of the structural theory of $n$-c.e. Turing degrees for $n>1$. We also discuss possible approaches to solution of the open problems.

Détail

Keywords: computably enumerable set, Turing degree, Ershov's hierarchy, definability.

Bibliographie

[1] Arslanov M. M., “Strukturnye svoistva stepenei nizhe $\boldsymbol{0}'$”, Dokl. AN SSSR, 283 (1985), 270–273 | Zbl

[2] Arslanov M. M., “O verkhnei polureshetke stepenei nizhe $\boldsymbol{0}'$”, Izv. vuzov Mat., 7 (1988), 27–33

[3] Arslanov M. M., “Strukturnaya teoriya stepenei nerazreshimosti: dostizheniya i otkrytye problemy”, Algebra i logika, 54:4 (2015), 529–535 | MR | Zbl

[4] Ershov Yu. L., “Ob odnoi ierarkhii mnozhestv”, I, Algebra i logika, 7 (1968), 47–73 | MR

[5] Ershov Yu. L., “Ob odnoi ierarkhii mnozhestv”, II, Algebra i logika, 7 (1968), 15–47 | MR | Zbl

[6] Ershov Yu. L., “Ob odnoi ierarkhii mnozhestv”, III, Algebra i logika, 9 (1970), 34–51 | MR

[7] Ershov Yu. L., Palyutin E. A., Matematicheskaya logika, Nauka, M., 1987 | MR

[8] Soar R., Vychislimo perechislimye mnozhestva i stepeni, Kazan. mat. ob-vo, Kazan, 2000

[9] Faizrakhmanov M. Kh., “Razlozhimost nizkikh $2$-vychislimo perechislimykh stepenei i tyuringovy skachki v ierarkhii Ershova”, Izv. vuzov Mat., 12 (2010), 58–66 | MR | Zbl

[10] Yamaleev M. M., “Razlozhimost $2$-vychislimo perechmslimykh stepenei s izbeganiem konusov”, Izv. vuzov Mat., 6 (2009), 76–80 | Zbl

[11] Yamaleev M. M., Strukturnye svoistva tyuringovykh stepenei mnozhestv iz ierarkhii Ershova, Diss. na soisk. uch. step. kand. fiz.-mat. nauk, KGU, Kazan, 2009

[12] Ambos-Spies K., Jockusch C. G. Jr., Shore R. A., Soare R. I., “An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees”, Trans. Am. Math. Soc., 281 (1984), 109–-128 | DOI | MR | Zbl

[13] Ambos-Spies K., Lerman M., “Lattice embeddings into the recursively enumerable degrees”, J. Symb. Logic, 51 (1986), 257–-272 | DOI | MR | Zbl

[14] Ambos-Spies K. Lerman M., “Lattice embeddings into the recursively enumerable degrees”, II, J. Symb. Logic, 54 (1989), 735–-760 | DOI | MR | Zbl

[15] Andrews U., Kuyper R., Lempp S., Soskova M., Yamaleev M. M., “Nondensity of double bubbles in the D.C.E. degrees”, Lect. Notes Comput. Sci., 10010 (2017), 547–562 | DOI | MR | Zbl

[16] Arslanov M. M., “Definable relations in Turing degree structures”, J. Logic Comput., 23:6 (2013), 1145–1154 | DOI | MR | Zbl

[17] Arslanov M. M., Cooper S. B., Li A., “There is no low maximal d.c.e. degree”, Math. Logic Quart., 46 (2000), 409–416 | 3.0.CO;2-P class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[18] Arslanov M. M., Cooper S. B., Li A., “There is no low maximal d.c.e. degree. Corrigendum”, Math. Logic Quart., 50 (2004), 628–636 | DOI | MR

[19] Arslanov M. M., Kalimullin I. Sh., Lempp S., “On Downey's conjecture”, J. Symb. Logic, 75 (2010), 401–441 | DOI | MR | Zbl

[20] Arslanov M. M., LaForte G. L., Slaman T. A., “Relative recursive enumerability in the difference hierarchy”, J. Symb. Logic, 63 (1998), 411–420 | DOI | MR | Zbl

[21] Arslanov M. M., Lempp S., Shore R. A., “On isolating r.e. and isolated $d$-r.e. degrees”, London Math. Soc. Lect. Note, 224 (1996), 61–80 | MR | Zbl

[22] Arslanov M. M., Lempp S., Shore R. A., “Interpolating $d$-r.e. and REA degrees between r.e. degrees”, Ann. Pure Appl. Logic, 78 (1996), 29–56 | DOI | MR | Zbl

[23] Barmpalias G., Cai M., Lempp S., Slaman T. A., “On the existence of a strong minimal pair”, J. Math. Logic, 15:1 (2015), 1550003 | DOI | MR | Zbl

[24] Cai M., Shore R. A., Slaman T. A., “The $n$-r.e. degrees: undecidability and $\Sigma_1$ substructures”, J. Math. Logic, 12 (2012), 1–30 | DOI | MR | Zbl

[25] Cholak P., “Automorphisms of the lattice of recursively enumerable sets”, Mem. Am. Math. Soc., 541 (1995) | MR | Zbl

[26] Cholak P., Harrington L., “On the definability of the double jump in the computably enumerable sets”, J. Math. Logic, 2 (2002), 261–296 | DOI | MR | Zbl

[27] Cooper S. B., Degrees of Unsolvability, Ph.D. Thesis, Leicester University, Leicester, 1971 | MR

[28] Cooper S. B., “The jump is definable in the structure of the degrees of unsolvability”, Bull. Am. Math. Soc. New Ser., 23:1 (1990), 151–158 | DOI | MR | Zbl

[29] Cooper S. B., “The density of the low$_2$ $n$-r.e. degrees”, Arch. Math. Logic, 31 (1991), 19–24 | DOI | MR | Zbl

[30] Cooper S. B., “A splitting theorem for the $n$-r.e. degrees”, Proc. Am. Math. Soc., 115 (1992), 461–471 | MR | Zbl

[31] Cooper S. B., Harrington L., Lachlan A. H., Lempp S., Soare R. I., “The $d$-r.e. degrees are not dense”, Ann. Pure Appl. Logic, 55 (1991), 125–151 | DOI | MR | Zbl

[32] Cooper S. B., Harrington L., Lachlan A. H., Lempp S., Soare R. I., “Corrigendum to «The d.r.e. degrees are not dense»”, Ann. Pure Appl. Logic, 168 (2017), 2164–2165 | DOI | MR | Zbl

[33] Cooper S. B., Li A., “Non-uniformity and generalised Sacks splitting”, Acta Math. Sinica. Engl. Ser., 18 (2002), 327–334 | DOI | MR | Zbl

[34] Cooper S. B., Li A., “Splitting and cone avoidance in the d.c.e. degrees”, Sci. China. Ser. A., 45 (2002), 1135–1146 | MR | Zbl

[35] Cooper S. B., Li A., “Turing definability in the Ershov hierarchy”, J. London Math. Soc. (2), 66 (2002), 513–528 | DOI | MR | Zbl

[36] Cooper S. B., Yi X., Isolated d.r.e. degrees, Universiry of Leeds, 1995

[37] Downey R. G., “D.r.e. degrees and the nondiamond theorem”, Bull. London Math. Soc., 21 (1989), 43–50 | DOI | MR | Zbl

[38] Downey R., Hirschfeldt D., Algorithmic randomness and complexity, Springer-Verlag, 2010 | MR | Zbl

[39] Downey R. G., Laforte G. A., Shore R. I., “Decomposition and infima in the computably enumerable degrees”, J. Symb. Logic, 68 (2003), 551–579 | DOI | MR | Zbl

[40] Downey R. G., Stob M., “Splitting theorems in recursion theory”, Ann. Pure Appl. Logic, 65 (1993), 1–106 | DOI | MR | Zbl

[41] Epstein R., “The nonlow computably enumerable degrees are not definable in ${\mathcal E}$”, Trans. Am. Math. Soc., 365 (2013), 1305–1345 | DOI | MR | Zbl

[42] Epstein R. L., Degrees of unsolvability: structure and theory, Springer-Verlag, Berlin–Heidelberg–New York, 1979 | MR | Zbl

[43] Fang Ch., Liu J., Wu G., Yamaleev M. M., “Nonexistence of minimal pairs in $L[\boldsymbol{d}]$”, Lect. Notes, Comput. Sci., 9136, 2015, 177–185 | MR | Zbl

[44] Fang Ch., Wu G., Yamaleev M. M., “On a problem of Ishmukhametov”, Arch. Math. Logic, 52 (2013), 733–741 | DOI | MR | Zbl

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

[46] Harrington L., Understanding Lachlan's monster paper, Manuscript, 1980

[47] Harrington L., Shelah S., “The undecidability of the recursively enumerable degrees (research announcement)”, Bull. Am. Math. Soc., 6:1 (1982), 79–80 | DOI | MR | Zbl

[48] Harrington L., Soare R. I., “The $\Delta_3^0$-automorphism method and noninvariant classes of degrees”, J. Am. Math. Soc., 9 (1996), 617–666 | DOI | MR | Zbl

[49] Ishmukhametov Sh. T., “Downward density of exact degrees”, Arch. Math. Logic, 38 (1999), 373–386 | DOI | MR | Zbl

[50] Ishmukhametov Sh. T., “On relative enumerability of Turing degrees”, Arch. Math. Logic, 39 (2000) | DOI | MR | Zbl

[51] Jockusch C. G., Jr., “Review of Lerman”, 12, Math. Reviews, 45:3200 (1973)

[52] Jockusch C., Shore R., “Pseudojump operators, II: Transfinite iterations, hierarchies and minimal covers”, J. Symb. Logic, 49 (1984), 1205–1236 | DOI | MR | Zbl

[53] Lachlan A. H., “Lower bounds for pairs of recursively enumerable degrees”, Proc. London Math. Soc., 16 (1966) | MR | Zbl

[54] Lachlan A. H., “The elementary theory of recursively enumerable sets”, Duke Math. J., 35 (1968), 123–146 | DOI | MR | Zbl

[55] Lachlan A. H., “Degrees of recursively enumerable sets which have no maximal supersets”, J. Symb. Logic, 33 (1968), 431–443 | DOI | MR | Zbl

[56] Lachlan A. H., “Distrubutive initial segments of the degrees of unsolvability”, Z. Math. Logik Grundlag. Math, 14 (1968), 457–472 | DOI | MR | Zbl

[57] Lachlan A. H., “On the lattice of recursively enumerable sets”, Trans. Am. Math. Soc., 130 (1968), 1–37 | DOI | MR | Zbl

[58] Lachlan A. H., “A recursively enumerable degree which will not split over all lesser ones”, Ann. Math. Logic, 9 (1975), 307–365 | DOI | MR

[59] Lempp S., Lerman M., Solomon D., “Embedding finite lattices into the computably enumerable degrees—a status survey”, «Logic Colloquium’02», Proc. Ann. Eur. Summer Meeting of the Association for Symbolic Logic, Lect. Notes Logic, 27, 2006, 206–229 | MR | Zbl

[60] Lempp S., Nies A., “Differences of computably enumerable sets”, Math. Log. Q., 46 (2000), 555–561 | 3.0.CO;2-2 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[61] Lempp S., Nies A., Slaman T. A., “The $\Pi_3$-theory of the computably enumerable Turing degrees is undecidable”, Trans. Am. Math. Soc., 350:7 (1998), 2719–2736 | DOI | MR | Zbl

[62] Lerman M., Degrees of unsolvability, Springer-Verlag, Berlin–Heidelberg–New York, 1983 | MR | Zbl

[63] Lerman M., “Embeddings into the recursively enumerable degrees”, Computability, Enumerability, Decidability: Directions in Recursion Theory, v. 224, Cambridge Univ. Press, Cambridge, 1996, 185–204 | DOI | MR | Zbl

[64] Lerman M., Shore R. A., “Decidability and invariant classes for degree structures”, Trans. Am. Math. Soc., 301:2 (1988), 669–692 | DOI | MR

[65] Lerman M. Shore R. A., Soare R. I., “The elementary theory of the recursively enumerable degrees is not $\aleph_0$-categorical”, Adv. Math., 53 (1984), 301–320 | DOI | MR | Zbl

[66] Li A., “The low splitting theorem in the difference hierarchy”, Lect. Notes Comp. Sci., 3526 (2005), 287–296 | DOI | Zbl

[67] Li A., Yi X., “Cupping the recursively enumerable degrees by d.r.e. degrees”, Proc. London Math. Soc. (3), 78 (1999), 1–21 | DOI | MR

[68] Liu J., Wu G., Yamaleev M. M., “Downward density of exact degrees”, Lobachevskii J. Math. (4), 36 (2015), 389–398 | DOI | MR | Zbl

[69] Martin D. A., “Classes of recursively enumerable sets and degrees of unsolvability”, Z. Math. Logik Grundl. Math., 12 (1966), 295–310 | DOI | MR | Zbl

[70] Miller D. P., “High recursively enumerable degrees and the anti-cupping property”, Lect. Notes, Math., 859, 1981, 230-–245 | MR | Zbl

[71] Nies A., Slaman T. A., Shore R. A., “Interpretability and definability in the recursively enumerable degrees”, Proc. Lon. Math. Soc. (3), 77 (1998), 241–291 | DOI | MR | Zbl

[72] Putnam H., “Trial and error predicates and the solution to a problem of Mostowski”, J. Symb. Logic, 30 (1965), 49–57 | DOI | MR | Zbl

[73] Robinson R. W., “Interpolation and embedding in the recursively enumerable degrees”, Ann. Math. (2), 93 (1971), 285–314 | DOI | MR | Zbl

[74] Rogers H., Jr., Theory of recursive functions and effective computability, McGraw Hill, New York, 1967 | MR | Zbl

[75] Sacks G. E., “A minimal degree less than $\boldsymbol{0}'$”, Bull. Am. Math. Soc., 67 (1961), 416–419 | DOI | MR | Zbl

[76] Sacks G. E., “On the degrees less than $\boldsymbol{0}'$”, Ann. Math. (2), 77 (1963), 211–231 | DOI | MR | Zbl

[77] Sacks G. E., “The recursively enumerable degrees are dense”, Ann. Math. (2), 80 (1964), 300–312 | DOI | MR | Zbl

[78] Shoenfield J. R., “Degrees of classes of RE sets”, J. Symb. Logic, 41 (1976), 695–696 | DOI | MR | Zbl

[79] Shore R. A., “On the $\forall\exists$-sentences of $\alpha$-recursive theory”, Generalized Recursion Theory, v. II, Proc. Second Symp. on Generalized Recursion Theory, Oslo, 1978, 1977 | MR

[80] Shore R. A., “Finitely generated codings and the degrees r.e. in a degree ${\boldsymbol{d}}$”, Proc. Am. Math. Soc., 84 (1982), 256–263 | MR | Zbl

[81] Shore R. A., Slaman T. A., “Working below a low$_2$ recursively enumerable degrees”, Arch. Math. Logic, 29 (1990), 201–211 | DOI | MR | Zbl

[82] Shore R. A., Slaman T. A., “A splitting theorem for $n$-REA degrees”, Proc. Am. Math. Soc., 129 (2001), 3721–3728 | DOI | MR | Zbl

[83] Slaman T. A., Soare R. I., “Algebraic aspects of the computably enumerable degrees”, Proc. Nat. Ac. Sci., 2 (1995), 617–621 | DOI | MR | Zbl

[84] Slaman T. A., Soare R. I., “Extension of embeddings in the computably enumerable degrees”, Ann. Math. (2), 154 (2001), 1–-43 | DOI | MR | Zbl

[85] Slaman T. A., Woodin W., “Definability in Turing degrees”, Ill. J. Math. (2), 30 (1986), 320–334 | DOI | MR | Zbl

[86] Welch L., A hierarchy of families of recursively enumerable degrees and a theorem on bounding minimal pairs, Ph.D. Thesis, University of Illinois, Urbana, 1980 | MR

[87] Wu G., “Isolation and lattice embedding”, J. Symb. Logic, 67 (2002), 1055–1064 | DOI | MR | Zbl

[88] Wu G., Yamaleev M. M., “Isolation: motivations and applications”, Uch. Zap. Kazan. Univ., Ser. Fiz.-Mat. Nauki, 154, 2, 2012, 204–-217 | MR

[89] Yang Y., Yu L., “On $\Sigma_1$-structural differences among Ershov hierarchies”, J. Symb. Logic, 71 (2006), 1223–1236 | DOI | MR | Zbl