matatecsМатематика и теоретические компьютерные наукиMathematics and Theoretical Computer Science2949-3919Казанский (Приволжский) федеральный университет10.26907/2949-3919.2026.1.47-66matatecs-104Research ArticleСТАТЬИВычислимые накрытия арифметических классов программных системComputable covers for arithmetical collections of programming systemsФайзрахмановМ. Х.FaizrahmanovM. Kh.

Марат Хайдарович Файзрахманов

Ул. Кремлевская, д. 18, Казань, 420008

Marat Khaidarovich Faizrahmanov

18 Kremlyovskaya str., Kazan 420008

marat.faizrahmanov@gmail.comКазанский (Приволжский) федеральный университет, Научно-образовательный математический центр ПФОРоссияKazan Federal University, Volga Region Mathematical CenterRussian Federation202622062026414766Copyright © Файзрахманов М.Х., 20262026Файзрахманов М.Х.Faizrahmanov M.K.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matatecs.elpub.ru/jour/article/view/104

В работе получены достаточные условия существования неглавных накрытий (относительно сводимости нумераций) классов нумераций, вычислимых в арифметической иерархии. Полученные условия, помимо прочего, позволяют построить неглавное вычислимое накрытие класса всех фридберговых нумераций и прояснить вопрос о возможных мощностях факторполурешеток Роджерса относительно арифметических идеалов. В работе также доказывается, что идеал полурешетки Роджерса семейства всех унарных частичных рекурсивных функций, порожденный прямыми суммами бесконечных последовательностей ее фридберговых атомов, является собственным подидеалом идеала всех его не наибольших элементов.

We obtain sufficient conditions for the existence of non-acceptable covers (with respect to the reducibility of numberings) for classes of numberings computable in the arithmetical hierarchy. These conditions, among other things, imply that the class of all Friedberg computable numberings has a non-acceptable computable cover and allow us to clarify the question of possible cardinalities of Rogers quotient semilattices with respect to arithmetical ideals. We also prove that the ideal in the Rogers semilattice of the family of all unary partial recursive functions generated by the direct sums of infinite sequences of its Friedberg-atoms is a proper subideal of the ideal of all its non-greatest elements.

вычислимая нумерациядопустимая нумерацияфридбергова нумерациякласс Роджерсаполурешетка Роджерсаcomputable numberingacceptable numberingFriedberg numberingRogers classRogers semilatticeРабота выполнена за счет предоставленного в 2026 году Фондом науки и технологий Республики Татарстан гранта на осуществление фундаментальных и прикладных научных работ в научных и образовательных организациях, предприятиях и организациях реального сектора экономики Республики ТатарстанThis work was supported by the Science and Technology Fund of the Republic of Tatarstan grant for the implementation of fundamental and applied scientific research in scientific and educational organizations, enterprises and organizations of the real sector of the economy of the Republic of TatarstanReferencesS.A. Badaev, S.S. Goncharov, A. Sorbi, Completeness and universality of arithmetical numberings, in: Computability and models, Springer US, Boston, MA, 2003, 11–44. DOI: https://doi.org/10.1007/978-1-4615-0755-0_2S.A. Badaev, S.S. Goncharov, A. Sorbi, Completeness and universality of arithmetical numberings, in: Computability and models, Springer US, Boston, MA, 2003, 11–44. DOI: https://doi.org/10.1007/978-1-4615-0755-0_2Ю.Л. Ершов, Полно нумерованные множества, Сиб. матем. журн. 10 (5), 1048–1064 (1969). URL: https://www.mathnet.ru/rus/smj5695Yu.L. Ershov, Completely enumerated sets, Siberian Math. J. 10 (5), 773–784 (1969). DOI: https://doi.org/10.1007/BF00971653Yu.L. Ershov, Theorie der numerierungen I, Z. Math. Logik Grundlagen Math. 19, 289–388 (1973) [in German]. DOI: https://doi.org/10.1002/malq.19730191901Yu.L. Ershov, Theorie der numerierungen I, Z. Math. Logik Grundlagen Math. 19, 289–388 (1973) [in German]. DOI: https://doi.org/10.1002/malq.19730191901Ю.Л. Ершов, Теория нумераций, Наука, М., 1977.Yu.L. Ershov, Theory of numberings, Nauka, M., 1977 [in Russian].Yu.L. Ershov, Theory of numberings, in: E.R. Griffor (ed.), Handbook of computability theory (Stud. Logic Found. Math., 140), Amsterdam, Elsevier, 1999, 473–503. DOI: https://doi.org/10.1016/S0049-237X(99)80030-5Yu.L. Ershov, Theory of numberings, in: E.R. Griffor (ed.), Handbook of computability theory (Stud. Logic Found. Math., 140), Amsterdam, Elsevier, 1999, 473–503. DOI: https://doi.org/10.1016/S0049-237X(99)80030-5Ю.Л. Ершов, Полурешетки Роджерса конечных частично упорядоченных множеств, Алгебра и логика 45 (1), 44–84 (2006). URL: https://www.mathnet.ru/rus/al117Yu.L. Ershov, Rogers semilattices of finite partially ordered sets, Algebra Logic 45 (1), 26–48 (2006). DOI: https://doi.org/10.1007/s10469-006-0004-9М.Х. Файзрахманов, Вложение первого неконструктивного ординала в полурешетки Роджерса семейств арифметических множеств, Сиб. матем. журн. 64 (4), 830–840 (2023). DOI: https://doi.org/10.33048/smzh.2023.64.414M. Faizrahmanov, Embedding of the first nonconstructive ordinal into the Rogers semilattices of families of arithmetic sets, Siberian Math. J. 64 (4), 927–935 (2023). DOI: https://doi/org/10.1134/S0037446623040146M. Faizrahmanov, Decomposition of Godel numberings into minimal numberings, J. Symb. Log. (published online, 2025). DOI: https://doi.org/10.1017/jsl.2025.10167M. Faizrahmanov, Decomposition of Godel numberings into minimal numberings, J. Symb. Log. (published online, 2025). DOI: https://doi.org/10.1017/jsl.2025.10167М.Х. Файзрахманов, О теореме Хуторецкого для обобщенно вычислимых семейств, Алгебра и логика 58 (4), 528–541 (2019). DOI: https://doi.org/10.33048/alglog.2019.58.408M. Faizrahmanov, Khutoretskii’s theorem for generalized computable families, Algebra Logic 58 (4), 256–365 (2019). DOI: https://doi.org/10.1007/s10469-019-09557-9R.M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symb. Log. 23 (3), 309–316 (1958). DOI: https://doi.org/10.2307/2964290R.M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symb. Log. 23 (3), 309–316 (1958). DOI: https://doi.org/10.2307/2964290С.С. Гончаров, А. Сорби, Обобщенно-вычислимые нумерации и тривиальные полурешетки Роджерса, Алгебра и логика 36 (6), 621–641 (1997). URL: https://www.mathnet.ru/rus/al2412S.S. Goncharov, A. Sorbi, Generalized computable numerations and nontrivial Rogers semilattices, Algebra Logic 36 (6), 359–369 (1997). DOI: https://doi.org/10.1007/bf02671553K. Harris, η-representation of sets and degrees, J. Symb. Log. 73 (4), 1097–1121 (2008). DOI: https://doi.org/10.2178/jsl/1230396908K. Harris, η-representation of sets and degrees, J. Symb. Log. 73 (4), 1097–1121 (2008). DOI: https://doi.org/10.2178/jsl/1230396908А.Б. Хуторецкий, О неглавных нумерациях, Алгебра и логика 8 (6), 726–732 (1969). URL: https://www.mathnet.ru/rus/al1228A.B. Khutoretskii, On nonprincipal enumerations, Algebra Logic 8 (6), 412–415 (1969). DOI: https://doi.org/10.1007/bf02219655А.Б. Хуторецкий, О мощности верхней полурешетки вычислимых нумераций, Алгебра и логика 10 (5), 561–569 (1971). URL: https://www.mathnet.ru/rus/al1317A.B. Khutoretskii, On the cardinality of the upper semilattice of computable enumerations, Algebra Logic 10 (5), 348–352 (1971). DOI: https://doi.org/10.1007/bf02219842M. Kummer, A note on direct sums of Friedbergnumberings, J. Symb. Log. 54 (3), 1009–1010 (1989). DOI: https://doi.org/10.2307/2274760M. Kummer, A note on direct sums of Friedbergnumberings, J. Symb. Log. 54 (3), 1009–1010 (1989). DOI: https://doi.org/10.2307/2274760A.H. Lachlan, A note on universal sets, J. Symb. Log. 31 (4), 574–574 (1966). DOI: https://doi.org/10.2307/2269692A.H. Lachlan, A note on universal sets, J. Symb. Log. 31 (4), 574–574 (1966). DOI: https://doi.org/10.2307/2269692С.С. Марченков, О вычислимых нумерациях семейств общерекурсивных функций, Алгебра и логика 11 (5), 588–607 (1972). URL: https://www.mathnet.ru/rus/al1353S.S. Marchenkov, The computable enumerations of families of general recursive functions, Algebra Logic 11 (5), 326–336 (1972). DOI: https://doi.org/10.1007/bf02330746Ш.Д. Нодиров, М.Х. Файзрахманов, Некоторые свойства классов минимальных нумераций семейств арифметических множеств, Матем. и теор. комп. науки 2 (1), 94–108 (2024). DOI: https://doi.org/10.26907/2949-3919.2024.1.94-108S. Nodirov, M. Faizrahmanov, Some properties of classes of minimal numberings of arithmetical set families, Mathematics and Theoretical Computer Sciences 2 (1), 94–108 (2024) [in Russian]. DOI: https://doi.org/10.26907/2949-3919.2024.1.94-108С.Ю. Подзоров, О предельности наибольшего элемента полурешетки Роджерса, Матем. тр. 7 (2), 98–108 (2004). URL: https://www.mathnet.ru/rus/mt78S.Y. Podzorov, Dual covers of the greatest element of the Rogers semilattice, Siberian Adv. Math. 15 (2), 104–114 (2005). URL: https://zbmath.org/?q=an:1095.03027С.Ю. Подзоров, Арифметические m-степени, Сиб. матем. журн. 49 (6), 1391–1410 (2008). URL: https://www.mathnet.ru/rus/smj1926S.Y. Podzorov, Arithmetical D-degrees, Siberian Math. J. 49 (6), 1109–1123 (2008). DOI: https://doi.org/10.1007/s11202-008-0107-8M.B. Pour-El, G¨odel numberings versus Friedberg numberings, Proc. AMS 15 (2), 252–256 (1964). DOI: https://doi.org/10.2307/2034045M.B. Pour-El, G¨odel numberings versus Friedberg numberings, Proc. AMS 15 (2), 252–256 (1964). DOI: https://doi.org/10.2307/2034045J.S. Royer, A connotational theory of program structure, Springer-Verlag, Berlin, 1987.J.S. Royer, A connotational theory of program structure, Springer-Verlag, Berlin, 1987.B. Schinzel, On decomposition of Godelnumberings into Friedbergnumberings, J. Symb. Log. 47 (2), 267–274 (1982). DOI: https://doi.org/10.2307/2273141B. Schinzel, On decomposition of Godelnumberings into Friedbergnumberings, J. Symb. Log. 47 (2), 267–274 (1982). DOI: https://doi.org/10.2307/2273141В.Л. Селиванов, Индексные множества фактор-объектов нумерации Поста, Алгебра и логика 27 (3), 343–358 (1988). URL: https://www.mathnet.ru/rus/al2020V.L. Selivanov, Index sets of quotient objects of the Post numeration, Algebra Logic 27 (3), 215–224 (1988). DOI: https://doi.org/10.1007/bf01978567V.L. Selivanov, Precomplete numberings, J. Math. Sci. 256 (1), 96–124 (2021). DOI: https://doi.org/10.1007/s10958-021-05422-2V.L. Selivanov, Precomplete numberings, J. Math. Sci. 256 (1), 96–124 (2021). DOI: https://doi.org/10.1007/s10958-021-05422-2R.I. Soare, Turing computability. Theory and applications o computability, Springer-Verlag, Berlin, 2016. DOI: https://doi.org/10.1007/978-3-642-31933-4R.I. Soare, Turing computability. Theory and applications of computability, Springer-Verlag, Berlin, 2016. DOI: https://doi.org/10.1007/978-3-642-31933-4S.A. Terwijn, Fixed point theorems in computability theory, in: Logics and type systems in theory and practice – essays dedicated to Herman Geuvers on the occasion of his 60th birthday, Springer, Cham, 2024, 214–224. DOI: https://doi.org/10.1007/978-3-031-61716-4_14S.A. Terwijn, Fixed point theorems in computability theory, in: Logics and type systems in theory and practice – essays dedicated to Herman Geuvers on the occasion of his 60th birthday, Springer, Cham, 2024, 214–224. DOI: https://doi.org/10.1007/978-3-031-61716-4_14

The authors declare that there are no conflicts of interest present.