Computably enumerable sets and related issues

I. A. Lavrov

Algebra i logika, Tome 50 (2011) no. 6, pp. 733-758.

Résumé

A topical direction in the theory of algorithms is studying reducibilities of arithmetic sets. Post defined concepts of $m$-, $tt$-, and $T$-reducibilities of arithmetic sets; subsequently, other kinds of reducibilities were introduced. A $T$-reducibility is being studied quite intensively today. Here a number of remarkable results were obtained. However, many questions concerning $T$-reducibility still await a solution. Progress in $tt$-reducibility is less noticeable. For an $m$-reducibility, exhaustive solutions were derived in several directions – especially if consideration was limited to computably enumerable sets. In the present review, we consider different aspects associated with computably enumerable sets and m-reducibility. Among these are an algebraic description of the structure of these formations both in upper and lower parts, definability, decidability problems, and so on. Many of the results cited in the paper are widely scattered over the literature. This makes it impossible to conceptualize the overall picture and spectrum of available investigations. It is also worth mentioning that a series of books and papers are not easily accessible to domestic specialists.

Détail

Keywords: computably enumerable set, $m$-reducibility.

Bibliographie

[1] A. I. Maltsev, Algoritmy i rekursivnye funktsii, Nauka, M., 1986 | MR

[2] V. A. Uspenskii, Lektsii o vychislimykh funktsiyakh, Fizmatgiz, M., 1960 | MR

[3] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977 ; Yu. L. Eršov, “Theorie der Numerierungen. I”, Z. Math. Logik Grundl. Math., 19:4 (1973), 289–388 ; “Theorie der Numerierungen. II”, Z. Math. Logik Grundl. Math., 21:6 (1975), 473–584 ; “Theorie der Numerierungen. III”, Z. Math. Logik Grundl. Math., 23:4 (1977), 289–371 | MR | MR | MR | DOI | MR

[4] R. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967 ; Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR | Zbl | MR

[5] P. Odifreddi, Classical recursion theory, v. I, Stud. Logic Found. Math., 125, North-Holland, Amsterdam etc., 1989 ; v. II, Stud. Logic Found. Math., 143, Elsevier, Amsterdam, 1999 | MR | Zbl | MR | Zbl

[6] A. N. Degtev, Perechislimye mnozhestva i svodimosti, Izd-vo TyumGU, Tyumen, 1988

[7] R. I. Soare, Recursively enumerable sets and degrees, A study of computable functions and computably generated sets, Perspect. Math. Log. Omega Series, Springer-Verlag, Berlin etc., 1987 ; R. I. Soar, Vychislimo perechislimye mnozhestva i stepeni, Izuchenie vychislimykh funktsii i vychislimo perechislimykh mnozhestv, Kazanskoe matem. ob-vo, Kazan, 2000 | MR | MR | Zbl

[8] J. R. Shoenfield, Degrees of unsolvability, North-Holland Math. Stud., 2, North-Holland Publ. Co., Amsterdam–London; American Elsevier Publ. Co. Inc., New York, 1971 ; Dzh. S. Shenfild, Stepeni nerazreshimosti, Nauka, M., 1977 | MR | Zbl | MR

[9] E. L. Post, “Recursively enumerable sets of positive integers and their decision problems”, Bull. Am. Math. Soc., 50:5 (1944), 284–316 | DOI | MR | Zbl

[10] P. A. Cholak, “The global structure of computabily enumerable sets”, Computability theory and its applications. Current trends and open problems, Proc. 1999 AMS–IMS–SIAM joint summer research conf. (Boulder, CO, USA, June 13–17, 1999), Contemporary Math., 257, eds. P. A. Cholak et al., Am. Math. Soc., Providence, RI, 2000, 61–72 | DOI | MR | Zbl

[11] P. Cholak, R. Downey, M. Stob, “Automorphisms of the lattice of recursively enumerable sets: Promptly simple sets”, Trans. Am. Math. Soc., 332:2 (1992), 555–570 | DOI | MR | Zbl

[12] P. A. Cholak, L. A. Harrington, “Definable encodings in the computably enumerable sets”, Bull. Symb. Log., 6:2 (2000), 185–196 | DOI | MR | Zbl

[13] P. A. Cholak, L. A. Harrington, “Isomorphisms of splits of computably enumerable sets”, J. Symb. Log., 68:3 (2003), 1044–1064 | DOI | MR | Zbl

[14] L. Harrington, R. I. Soare, “Post's program and incomplete recursively enumerable sets”, Proc. Natl. Acad. Sci. USA, 88:22 (1991), 10242–10246 | DOI | MR | Zbl

[15] L. Harrington, R. I. Soare, “Definability, automorphisms and dynamic properties of computably enumerable sets”, Bull. Symb. Log., 2:2 (1996), 199–213 | DOI | MR | Zbl

[16] L. Harrington, R. I. Soare, “Dynamic properties of computably enumerable sets”, Computability, enumerability, unsolvability, Directions in recursion theory, Lond. Math. Soc. Lect. Note Ser., 224, eds. S. B. Cooper et al., Cambridge Univ. Press, Cambridge, 1996, 105–121 | MR | Zbl

[17] R. I. Soare, “An overview of the computably enumerable sets”, Handbook of computability theory, Stud. Logic Found. Math., 140, ed. E. R. Griffor, Elsevier, Amsterdam, 1999, 199–248 | DOI | MR | Zbl

[18] R. I. Soare, “The history and concept of computability”, Handbook of computability theory, Stud. Logic Found. Math., 140, ed. E. R. Griffor, Elsevier, Amsterdam, 1999, 3–36 | DOI | MR | Zbl

[19] R. I. Soare, “Extensions, automorphisms and definability”, Computability theory and its applications. Current trends and open problems, Proc. 1999 AMS–IMS–SIAM joint summer research conf. (Boulder, CO, USA, June 13–17, 1999), Contemp. Math., 257, eds. P. A. Cholak et al., Am. Math. Soc., Providence, RI, 2000, 279–307 | DOI | MR | Zbl

[20] A. H. Lachlan, “On the lattice of recursively enumerable sets”, Trans. Am. Math. Soc., 130:1 (1968), 1–37 ; A. Kh. Lakhlan, “Reshetka rekursivno perechislimykh mnozhestv”, Stepeni nerazreshimosti, ed. Dzh. S. Shenfild, Nauka, M., 1977, 109–162 | DOI | MR | Zbl | MR

[21] R. M. Friedberg, “Three theorems on recursive enumeration. I. Decomposition, II. Maximal set, III. Enumeration without duplication”, J. Symb. Log., 23:3 (1958), 309–316 | DOI | MR

[22] A. A. Muchnik, “Nerazreshimost problemy svodimosti teorii algoritmov”, DAN SSSR, 108:2 (1956), 194–197 | Zbl

[23] S. D. Denisov, “Ob $m$-stepenyakh rekursivno perechislimykh mnozhestv”, Algebra i logika, 9:4 (1970), 422–427 | MR | Zbl

[24] G. E. Sacks, “On degrees less than $0'$”, Ann. Math. (2), 77:2 (1963), 211–231 | DOI | MR | Zbl

[25] Yu. L. Ershov, “Gipergiperprostye $m$-stepeni”, Algebra i logika, 8:5 (1969), 523–552 | MR | Zbl

[26] A. N. Degtev, “Ob $m$-stepenyakh prostykh mnozhestv”, Algebra i logika, 11:2 (1972), 130–139 | MR | Zbl

[27] A. H. Lachlan, “Recursively enumerable many-one degrees,”, Algebra i logika, 11:3 (1972), 326–358 | MR | Zbl

[28] A. H. Lachlan, “Two theorems on many-one degrees of recursively enumerable sets”, Algebra i logika, 11:2 (1972), 216–229 | MR | Zbl

[29] G. N. Kobzev, “O $btt$-svodimosti. II”, Algebra i logika, 12:4 (1973), 433–444 | MR | Zbl

[30] W. Maass, “Characterization of recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable sets”, Trans. Am. Math. Soc., 279:1 (1983), 311–336 | DOI | MR | Zbl

[31] W. Maass, M. Stob, “The intervals of the lattice of recursively enumerable sets determined by major subsets”, Ann. Pure Appl. Logic, 24:2 (1983), 189–212 | DOI | MR | Zbl

[32] R. W. Robinson, “Simplicity of recursively enumerable sets”, J. Symb. Log., 32:2 (1967), 162–172 | DOI | MR | Zbl

[33] P. A. Cholak, A. Nies, “Atomless $r$-maximal sets”, Isr. J. Math., 113 (1999), 305–322 | DOI | MR | Zbl

[34] D. A. Martin, “A theorem on hyperhypersimple sets”, J. Symb. Log., 28:4 (1963), 273–278 | DOI | MR

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

[36] J. S. Ullian, “A theorem on maximal sets”, Notre Dame J. Formal Logic, 2:4 (1961), 222–223 | DOI | MR | Zbl

[37] R. W. Robinson, “A dichotomy of the recursively enumerable sets”, Z. Math. Logik Grundl. Math., 14:4 (1968), 339–356 | DOI | MR | Zbl

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

[39] C. E. M. Yates, “Recursively enumerable sets and retracing functions”, Z. Math. Logik Grundl. Math., 8:4 (1962), 331–345 | DOI | MR | Zbl

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

[41] M. Lerman, “Some theorems on r-maximal sets and major subsets of recursively enumerable sets”, J. Symb. Log., 36:2 (1971), 193–215 | DOI | MR | Zbl

[42] M. Lerman, R. I. Soare, “A decidable fragment of the elementary theory of the lattice of recursively enumerable sets”, Trans. Am. Math. Soc., 257:1 (1980), 1–37 | DOI | MR | Zbl

[43] A. H. Lachlan, “A note on universal sets”, J. Symb. Log., 31:4 (1966), 573–574 | DOI | MR | Zbl

[44] S. D. Denisov, “Stroenie verkhnei polureshëtki rekursivno perechislimykh $m$-stepenei i smezhnye voprosy. 1”, Algebra i logika, 17:6 (1978), 643–683 | MR | Zbl

[45] Yu. L. Ershov, “Verkhnyaya polureshëtka numeratsii konechnogo mnozhestva”, Algebra i logika, 14:3 (1975), 258–284 | MR | Zbl

[46] E. A. Palyutin, “Dopolnenie k state Yu. L. Ershova ‘Verkhnyaya polureshëtka numeratsii konechnogo mnozhestva’ ”, Algebra i logika, 14:3 (1975), 284–287 | MR | Zbl

[47] Yu. L. Ershov, “Pozitivnye ekvivalentnosti”, Algebra i logika, 10:6 (1971), 620–650 | Zbl

[48] A. N. Degtev, “Ob $m$-stepenyakh nadmnozhestv prostykh mnozhestv”, Matem. zametki, 23:6 (1978), 889–893 | MR | Zbl

[49] Yu. L. Ershov, “Gipergiperprostye $m$-stepeni”, Algebra i logika, 8:5 (1969), 523–552 | MR | Zbl

[50] A. N. Degtev, “O $tt$- i $m$-stepenyakh”, Algebra i logika, 12:2 (1973), 143–161 | MR | Zbl

[51] Yu. L. Ershov, I. A. Lavrov, “Verkhnyaya polureshëtka $L(\gamma)$”, Algebra i logika, 12:2 (1973), 167–189 | MR | Zbl

[52] K. Ho, F. Stephan, Simple sets and strong reducibilities, Forschungsberichte Math. Logic, 45, Math. Inst. Univ., Heidelberg, 1999

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

[54] V. V. Vyugin, “Segmenty rekursivno perechislimykh $m$-stepenei”, Algebra i logika, 13:6 (1974), 635–654 | MR

[55] I. A. Lavrov, “Ob odnom svoistve kreativnykh mnozhestv”, Algebra i logika, 35:3 (1996), 294–307 | MR | Zbl

[56] L. A. Harrington, A. Nies, “Coding in the partial order of enumerable sets”, Adv. Math., 133:1 (1998), 133–162 | DOI | MR | Zbl

[57] A. N. Degtev, “Razreshimost $\forall\exists$-teorii nekotoroi faktor reshëtki rekursivno perechislimykh mnozhestv”, Algebra i logika, 17:2 (1978), 134–143 | MR | Zbl

[58] E. Herrmann, “On the $\forall\exists$-theory of the factor lattice by the major subset relation”, Computability, enumerability, unsolvability, Directions in recursion theory, Lond. Math. Soc. Lect. Note Ser., 224, eds. S. B. Cooper et al., Cambridge Univ. Press, Cambridge, 1996, 139–166 | MR | Zbl

[59] A. Nies, Coding method in computability theory and complexity theory, Habilitationsschrift, Univ. Heidelberg, 1998

[60] L. A. Harrington, The undecidability of the lattice of recursively enumerable sets, handwritten notes, 1983

[61] E. Herrmann, “The undecidability of the elementary theory of the lattice of recursively enumerable sets”, Frege conference 1984, Proc. the second int. conf. (Schwerin, September 10–14, 1984), Math. Res., 20, ed. G. Wechsung, Akademie-Verlag, Berlin, 1984, 66–72 | MR

[62] A. Nis, “Poslednii vopros o rekursivno-perechislimykh $m$-stepenyakh”, Algebra i logika, 33:5 (1994), 550–563 | MR

[63] A. Nies, “Model theory of the computably enumerable many-one degrees”, Log. J. IGPL, 8:5 (2000), 701–706 | DOI | MR | Zbl

[64] A. N. Degtev, “Neskolko rezultatov o verkhnikh polureshëtkakh i $m$-stepenyakh”, Algebra i logika, 18:6 (1979), 664–679 | MR | Zbl

[65] A. Nies, “Undecidable fragments of elementary theories”, Algebra Univers., 35:1 (1996), 8–33 | DOI | MR | Zbl

[66] R. M. Smullyan, Theory of formal systems, Annals Math. Stud., 47, Princeton Univ. Press, Princeton, N.J., 1961 ; R. Smalyan, Teoriya formalnykh sistem, Nauka, M., 1981 | MR | Zbl | MR

[67] Yu. L. Ershov, I. A. Lavrov, “O vychislimykh numeratsiyakh. II”, Algebra i logika, 8:1 (1969), 65–71 | MR | Zbl

[68] A. A. Muchnik, “Izomorfizm sistem rekursivno perechislimykh mnozhestv s effektivnymi svoistvami”, Trudy Mosk. matem. ob-va, 7, 1958, 407–412 | Zbl