Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
K. Ambos-Spies, C. G. Jockusch Jr., R. A. Shore, and R. I. Soare, “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, 109–128 (1984).
K. Ambos-Spies and M. Lerman, “Lattice embeddings into the recursively enumerable degrees,” J. Symb. Logic, 51, 257–272 (1986).
K. Ambos-Spies and M. Lerman, “Lattice embeddings into the recursively enumerable degrees, II,” J. Symb. Logic, 54, 735–760 (1989).
U. Andrews, R. Kuyper, S. Lempp, M. Soskova, and M. M. Yamaleev, “Nondensity of double bubbles in the D.C.E. degrees,” Lect. Notes Comput. Sci., 10010, 547–562 (2017).
M. M. Arslanov, “Structural properties of degrees below 0’,” Dokl. Akad. Nauk SSSR, 283, 270–273 (1985).
M. M. Arslanov, “The lattice of the degrees below 0’,” Izv. Vyssh. Ucheb. Zaved. Mat., 7, 27–33 (1988).
M. M. Arslanov, “Definable relations in Turing degree structures,” J. Logic Comput., 23, No. 6, 1145–1154 (2013).
M. M. Arslanov, “Structural theory of degrees of unsolvability: Achievements and open problems,” Algebra Logika, 54, No. 4, 529–535 (2015).
M. M. Arslanov, S. B. Cooper, and A. Li, “There is no low maximal d.c.e. degree,” Math. Logic Quart., 46, 409–416 (2000).
M. M. Arslanov, S. B. Cooper, and A. Li, “There is no low maximal d.c.e. degree. Corrigendum,” Math. Logic Quart., 50, 628–636 (2004).
M. M. Arslanov, I. Sh. Kalimullin, and S. Lempp, “On Downey’s conjecture,” J. Symb. Logic, 75, 401–441 (2010).
M. M. Arslanov, G. L. LaForte, and T. A. Slaman, “Relative recursive enumerability in the difference hierarchy,” J. Symb. Logic, 63, 411–420 (1998).
M. M. Arslanov, S. Lempp, and R. A. Shore, “On isolating r.e. and isolated d-r.e. degrees,” London Math. Soc. Lect. Notes, 224, 61–80 (1996).
M. M. Arslanov, S. Lempp, and R. A. Shore, “Interpolating d-r.e. and REA degrees between r.e. degrees,” Ann. Pure Appl. Logic, 78, 29–56 (1996).
G. Barmpalias, M. Cai, S. Lempp, and T. A. Slaman, “On the existence of a strong minimal pair,” J. Math. Logic, 15, No. 1, 1550003 (2015).
M. Cai, R. A. Shore, and T. A. Slaman, “The n-r.e. degrees: undecidability and Σ1 substructures,” J. Math. Logic, 12, 1–30 (2012).
P. Cholak, “Automorphisms of the lattice of recursively enumerable sets,” Mem. Am. Math. Soc., 541 (1995).
P. Cholak and L. Harrington, “On the definability of the double jump in the computably enumerable sets,” J. Math. Logic, 2, 261–296 (2002).
S. B. Cooper, Degrees of Unsolvability, Ph.D. Thesis, Leicester Univ., Leicester (1971).
S. B. Cooper, “The jump is definable in the structure of the degrees of unsolvability,” Bull. Am. Math. Soc. New Ser., 23, No. 1, 151–158 (1990).
S. B. Cooper, “The density of the low2 n-r.e. degrees,” Arch. Math. Logic, 31, 19–24 (1991).
S. B. Cooper, “A splitting theorem for the n-r.e. degrees,” Proc. Am. Math. Soc., 115, 461–471 (1992).
S. B. Cooper, L. Harrington, A. H. Lachlan, S. Lempp, and R. I. Soare, “The d-r.e. degrees are not dense,” Ann. Pure Appl. Logic, 55, 125–151 (1991).
S. B. Cooper, L. Harrington, A. H. Lachlan, S. Lempp, and R. I. Soare, “Corrigendum to “The d.r.e. degrees are not dense,” Ann. Pure Appl. Logic, 168, 2164–2165 (2017).
S. B. Cooper and A. Li, “Non-uniformity and generalised Sacks splitting,” Acta Math. Sinica. Engl. Ser., 18, 327–334 (2002).
S. B. Cooper and A. Li, “Splitting and cone avoidance in the d.c.e. degrees,” Sci. China. Ser. A., 45, 1135–1146 (2002).
S. B. Cooper and A. Li, “Turing definability in the Ershov hierarchy,” J. London Math. Soc. (2), 66, 513–528 (2002).
S. B. Cooper and X. Yi, Isolated d.r.e. degrees, Univ. of Leeds (1995).
R. G. Downey, “D.r.e. degrees and the nondiamond theorem,” Bull. London Math. Soc., 21, 43–50 (1989).
R. Downey and D. Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag (2010).
R. G. Downey, G. A. Laforte, and R. I. Shore, “Decomposition and infima in the computably enumerable degrees,” J. Symb. Logic, 68, 551–579 (2003).
R. G. Downey and M. Stob, “Splitting theorems in recursion theory,” Ann. Pure Appl. Logic, 65, 1–106 (1993).
R. Epstein, “The nonlow computably enumerable degrees are not definable in 𝜀,” Trans. Am. Math. Soc., 365, 1305–1345 (2013).
R. L. Epstein, Degrees of Unsolvability: Structure and Theory, Lect. Notes Math., 759, Springer-Verlag, Berlin–Heidelberg–New York (1979).
Yu. L. Ershov, “On a hierarchy of sets, I,” Algebra Logika, 7, 47–73 (1968).
Yu. L. Ershov, “On a hierarchy of sets, II,” Algebra Logika, 7, 15–47 (1968).
Yu. L. Ershov, “On a hierarchy of sets, III,” Algebra Logika, 9, 34–51 (1970).
Yu. L. Ershov and E. A. Palyutin, Mathematical Logic [in Russian], Nauka, Moscow (1987).
C. Fang, J. Liu, G. Wu, and M. M. Yamaleev, “Nonexistence of minimal pairs in L[d],” in: Lect. Notes Comput. Sci., 9136 (2015), pp. 177–185.
C. Fang, G. Wu, and M. M. Yamaleev, “On a problem of Ishmukhametov,” Arch. Math. Logic, 52, 733–741 (2013).
M. Kh. Faizrakhmanov, “Decomposability of low 2-computably enumerable degrees and Turing jumps in the Ershov hierarchy,” Izv. Vyssh. Ucheb. Zaved. Mat., 12, 58–66 (2010).
L. Feiner, “Hierarchies of Boolean algebras,” J. Symb. Logic, 35, 305–373 (1970).
L. Harrington, Understanding Lachlan’s monster paper, manuscript (1980).
L. Harrington and S. Shelah, “The undecidability of the recursively enumerable degrees (research announcement),” Bull. Am. Math. Soc., 6, No. 1, 79–80 (1982).
L. Harrington and R. I. Soare, “The \( {\Delta}_3^0 \)-automorphism method and noninvariant classes of degrees,” J. Am. Math. Soc., 9, 617–666 (1996).
Sh. T. Ishmukhametov, “Downward density of exact degrees,” Arch. Math. Logic, 38, 373–386 (1999).
Sh. T. Ishmukhametov, “On relative enumerability of Turing degrees,” Arch. Math. Logic, 39, 145–154 (2000).
C. G. Jockusch Jr., “Review of Lerman,” Math. Rev., 45, No. 3200 (1973).
C. Jockusch and R. Shore, “Pseudojump operators, II: Transfinite iterations, hierarchies and minimal covers,” J. Symb. Logic, 49, 1205–1236 (1984).
A. H. Lachlan, “Lower bounds for pairs of recursively enumerable degrees,” Proc. London Math. Soc., 16, 537–569 (1966).
A. H. Lachlan, “The elementary theory of recursively enumerable sets,” Duke Math. J., 35, 123– 146 (1968).
A. H. Lachlan, “Degrees of recursively enumerable sets which have no maximal supersets,” J. Symb. Logic, 33, 431–443 (1968).
A. H. Lachlan, “Distrubutive initial segments of the degrees of unsolvability,” Z. Math. Logik, 14, 457–472 (1968).
A. H. Lachlan, “On the lattice of recursively enumerable sets,” Trans. Am. Math. Soc., 130, 1–37 (1968).
A. H. Lachlan, “A recursively enumerable degree which will not split over all lesser ones,” Ann. Math. Logic, 9, 307–365 (1975).
S. Lempp, M. Lerman, and D. Solomon, “Embedding finite lattices into the computably enumerable degrees—a status survey,” in: Proc. Ann. Eur. Summer Meeting of the Association for Symbolic Logic “Logic Colloquium’02”, Lect. Notes Logic, 27 (2006), pp. 206–229.
S. Lempp and A. Nies, “Differences of computably enumerable sets,” Math. Logic Quart., 46, 555–561 (2000).
S. Lempp, A. Nies, and T. A. Slaman, “The Π3-theory of the computably enumerable Turing degrees is undecidable,” Trans. Am. Math. Soc., 350, No. 7, 2719–2736 (1998).
M. Lerman, Degrees of Unsolvability, Springer-Verlag, Berlin–Heidelberg–New York (1983).
M. Lerman, “Embeddings into the recursively enumerable degrees,” in: Computability, Enumerability, Decidability: Directions in Recursion Theory, London Math. Soc. Lect. Notes, 224 (S. B. Cooper, T. A. Slaman, and S. S. Wainer, eds.), Cambridge Univ. Press, Cambridge (1996), pp. 185–204.
M. Lerman and R. A. Shore, “Decidability and invariant classes for degree structures,” Trans. Am. Math. Soc., 301, No. 2, 669–692 (1988).
M. Lerman, R. A. Shore, and R. I. Soare, “The elementary theory of the recursively enumerable degrees is not ℵ0-categorical,” Adv. Math., 53, 301–320 (1984).
A. Li in: Lect. Notes Comput. Sci., 3526 (2005), pp. 287–296.
A. Li and X. Yi, “Cupping the recursively enumerable degrees by d.r.e. degrees,” Proc. London Math. Soc. (3), 78, 1–21 (1999).
J. Liu, G. Wu, and M. M. Yamaleev, “Downward density of exact degrees,” Lobachevskii J. Math. (4), 36, 389–398 (2015).
D. A. Martin, “Classes of recursively enumerable sets and degrees of unsolvability,” Z. Math. Logik, 12, 295–310 (1966).
D. P. Miller, “High recursively enumerable degrees and the anti-cupping property,” Lect. Notes Math., 859, 230– 245 (1981).
A. Nies, T. A. Slaman, and R. A. Shore, “Interpretability and definability in the recursively enumerable degrees,” Proc. London Math. Soc. (3), 77, 241–291 (1998).
H. Putnam, “Trial and error predicates and the solution to a problem of Mostowski,” J. Symb. Logic, 30, 49–57 (1965).
R. W. Robinson, “Interpolation and embedding in the recursively enumerable degrees,” Ann. Math. (2), 93, 285–314 (1971).
H. Rogers Jr., Theory of Recursive Functions and Effective Computability, McGraw Hill, New York (1967).
G. E. Sacks, “A minimal degree less than 0’,” Bull. Am. Math. Soc., 67, 416–419 (1961).
G. E. Sacks, “On the degrees less than 0’,” Ann. Math. (2), 77, 211–231 (1963).
G. E. Sacks, “The recursively enumerable degrees are dense,” Ann. Math. (2), 80, 300–312 (1964).
J. R. Shoenfield, “Degrees of classes of RE sets,” J. Symb. Logic, 41, 695–696 (1976).
R. A. Shore, “On the ∀∃-sentences of α-recursive theory,” in: Proc. Second Symp. “Generalized Recursion Theory,” Oslo, 1977, Vol. II, Oslo (1978).
R. A. Shore, “Finitely generated codings and the degrees r.e. in a degree d,” Proc. Am. Math. Soc., 84, 256–263 (1982).
R. A. Shore and T. A. Slaman, “Working below a low2 recursively enumerable degrees,” Arch. Math. Logic, 29, 201–211 (1990).
R. A. Shore and T. A. Slaman, “A splitting theorem for n-REA degrees,” Proc. Am. Math. Soc., 129, 3721–3728 (2001).
T. A. Slaman and R. I. Soare, “Algebraic aspects of the computably enumerable degrees,” Proc. Natl. Acad. Sci., 2, 617–621 (1995).
T. A. Slaman and R. I. Soare, “Extension of embeddings in the computably enumerable degrees,” Ann. Math. (2), 154, 1–43 (2001).
T. A. Slaman and W. Woodin, “Definability in Turing degrees,” Ill. J. Math. (2), 30, 320–334 (1986).
R. Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets, Springer-Verlag, Berlin (1987).
L. Welch, A hierarchy of families of recursively enumerable degrees and a theorem on bounding minimal pairs, Ph.D. Thesis, Univ. of Illinois, Urbana (1980).
G. Wu, “Isolation and lattice embedding,” J. Symb. Logic, 67, 1055–1064 (2002).
G. Wu and M. M. Yamaleev, “Isolation: motivations and applications,” Uch. Zap. Kazan. Univ. Ser. Fiz.-Mat. Nauki, 154, 204–217 (2012).
M. M. Yamaleev, “Splitting of 2-computably enumerable degrees with avoiding cones,” Izv. Vyssh. Ucheb. Zaved. Mat., 6, 76–80 (2009).
M. M. Yamaleev, Structural properties of Turing degrees of sets from the Ershov hierarchy, Ph.D. thesis, Kazan State Univ., Kazan (2009).
Y. Yang and L. Yu, “On Σ1-structural differences among Ershov hierarchies,” J. Symb. Logic, 71, 1223–1236 (2006).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Itogi Nauki i Tekhniki, Seriya Sovremennaya Matematika i Ee Prilozheniya. Tematicheskie Obzory, Vol. 157, Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University, 2018.
Rights and permissions
About this article
Cite this article
Arslanov, M.M., Yamaleev, M.M. Turing Computability: Structural Theory. J Math Sci 256, 1–33 (2021). https://doi.org/10.1007/s10958-021-05418-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-021-05418-y