Effectively infinite classes of numberings of computable families of reals

M. Kh. Faizrahmanov

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 5 (2023), pp. 96-100.

Résumé

Results on the effective infinity of classes of all (single-valued) numberings of families of all left-c.e. and all Martin-Löf random left-c.e. reals are presented, as well as sufficient conditions for the effective infinity of classes of numberings of families of computably enumerable sets aimed at obtaining them.

Détail

Keywords: computable numbering, single-valued numbering, positive numbering, effective infinity, left-c.e. real.

Bibliographie

[1] Goncharov S.S., Yakhnis A., Yakhnis V., “Some effectively infinite classes of enumerations”, Ann. Pure Appl. Logic, 60:3 (1993), 207–235 | DOI | MR | Zbl

[2] Brodhead P., Kjos-Hanssen B., “Numberings and randomness”, Mathematical theory and computational practice, CiE 2009, Lect. Notes Comput. Sci., 5635, eds. Ambos-Spies K., Löwe B., Merkle W., Springer, Berlin–Heidelberg, 2009 | MR

[3] Faizrahmanov M., Kalimullin I., “Limitwise monotonic sets of reals”, Math. Logic. Quart., 61:3 (2015), 224–229 | DOI | MR | Zbl

[4] Faizrahmanov M., “Limitwise monotonic spectra and their generalizations”, Connecting with computability, CiE 2021, Lect. Notes Comput. Sci., 12813, eds. De Mol L., Weiermann A., Manea F., Fernández-Duque D., Springer, Cham, 2021 | MR

[5] Nies A., Computability and randomness, Oxford Univ. Press, 2009 | MR | Zbl

[6] Vereschagin N.K., Uspenskii V.A., Shen A., Kolmogorovskaya slozhnost i algoritmicheskaya sluchainost, MTsNMO, M., 2013

[7] Ershov Yu.L., Teoriya numeratsii, Nauka, M., 1997 | MR

[8] Ershov Yu.L., “Theory of numberings”, Handbook of computability theory, Stud. Logic Found. Math., 140, Elsevier, Amsterdam, 1999 | MR | Zbl

[9] Soare R.I., Recursively enumerable sets and degrees. A study of computable funtions and computably generated sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987 | DOI | MR

[10] Soare R.I., Turing computability. Theory and applications, Springer, Berlin, 2016 | MR | Zbl

[11] Goncharov S.S., Sorbi A., “Obobschenno-vychislimye numeratsii i netrivialnye polureshetki Rodzhersa”, Algebra i logika, 36:6 (1997), 621–641 | MR | Zbl

[12] Goncharov S.S., “Semeistvo s edinstvennoi odnoznachnoi, no ne naimenshei numeratsiei”, Tr. In-ta Matem., 8 (1988), 42–58 | Zbl

[13] Kummer M., “An easy priority-free proof of a theorem of Friedberg”, Theoret. Comput. Sci., 74:2 (1990), 249–251 | DOI | MR | Zbl

[14] Myhill J., “Creative sets”, Z. Math. Logik und Grundlag. Math., 1:2 (1955), 97–108 | DOI | MR | Zbl

[15] Badaev S.A., “O pozitivnykh numeratsiyakh”, Sib. matem. zhurn., 18:3 (1977), 483–496 | MR | Zbl

[16] Badaev S.A., Podzorov S.Yu., “Minimalnye nakrytiya v polureshetkakh Rodzhersa $\Sigma^0_n$-vychislimykh numeratsii”, Sib. matem. zhurn., 43:4 (2002), 769—778 | MR | Zbl

[17] Podzorov S.Yu., “Nachalnye segmenty v polureshetkakh Rodzhersa $\Sigma^0_n$-vychislimykh numeratsii”, Algebra i logika, 42:2 (2003), 211–226 | MR | Zbl

[18] Badaev S.A., Goncharov S.S., Sorbi A., “Ob elementarnykh teoriyakh polureshetok Rodzhersa”, Algebra i logika, 44:3 (2005), 261–268 | MR | Zbl

[19] Badaev S.A., Goncharov S.S., Sorbi A., “Tipy izomorfizmov polureshetok Rodzhersa semeistv iz razlichnykh urovnei arifmeticheskoi ierarkhii”, Algebra i logika, 45:6 (2006), 637–654 | MR | Zbl

[20] Badaev S.A., Goncharov S.S., “O polureshetkakh Rodzhersa semeistv arifmeticheskikh mnozhestv”, Algebra i logika, 40:5 (2001), 507–522 | MR | Zbl

[21] Faizrakhmanov M.Kh., “Minimalnye obobschenno vychislimye numeratsii i vysokie stepeni”, Sib. matem. zhurn., 58:3 (2017), 710–716 | MR