Вычислимые накрытия арифметических классов программных систем
https://doi.org/10.26907/2949-3919.2026.1.47-66
Аннотация
В работе получены достаточные условия существования неглавных накрытий (относительно сводимости нумераций) классов нумераций, вычислимых в арифметической иерархии. Полученные условия, помимо прочего, позволяют построить неглавное вычислимое накрытие класса всех фридберговых нумераций и прояснить вопрос о возможных мощностях факторполурешеток Роджерса относительно арифметических идеалов. В работе также доказывается, что идеал полурешетки Роджерса семейства всех унарных частичных рекурсивных функций, порожденный прямыми суммами бесконечных последовательностей ее фридберговых атомов, является собственным подидеалом идеала всех его не наибольших элементов.
Ключевые слова
вычислимая нумерация,
допустимая нумерация,
фридбергова нумерация,
класс Роджерса,
полурешетка Роджерса
При поддержке: Работа выполнена за счет предоставленного в 2026 году Фондом науки и технологий Республики Татарстан гранта на осуществление фундаментальных и прикладных научных работ в научных и образовательных организациях, предприятиях и организациях реального сектора экономики Республики Татарстан
Об авторе
М. Х. Файзрахманов
Казанский (Приволжский) федеральный университет, Научно-образовательный математический центр ПФО
Россия
Россия
Марат Хайдарович Файзрахманов
Ул. Кремлевская, д. 18, Казань, 420008
Список литературы
1. S.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
2. Ю.Л. Ершов, Полно нумерованные множества, Сиб. матем. журн. 10 (5), 1048–1064 (1969). URL: https://www.mathnet.ru/rus/smj5695
3. Yu.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
4. Ю.Л. Ершов, Теория нумераций, Наука, М., 1977.
5. 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-5
6. Ю.Л. Ершов, Полурешетки Роджерса конечных частично упорядоченных множеств, Алгебра и логика 45 (1), 44–84 (2006). URL: https://www.mathnet.ru/rus/al117
7. М.Х. Файзрахманов, Вложение первого неконструктивного ординала в полурешетки Роджерса семейств арифметических множеств, Сиб. матем. журн. 64 (4), 830–840 (2023). DOI: https://doi.org/10.33048/smzh.2023.64.414
8. M. Faizrahmanov, Decomposition of Godel numberings into minimal numberings, J. Symb. Log. (published online, 2025). DOI: https://doi.org/10.1017/jsl.2025.10167
9. М.Х. Файзрахманов, О теореме Хуторецкого для обобщенно вычислимых семейств, Алгебра и логика 58 (4), 528–541 (2019). DOI: https://doi.org/10.33048/alglog.2019.58.408
10. R.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
11. С.С. Гончаров, А. Сорби, Обобщенно-вычислимые нумерации и тривиальные полурешетки Роджерса, Алгебра и логика 36 (6), 621–641 (1997). URL: https://www.mathnet.ru/rus/al2412
12. K. Harris, η-representation of sets and degrees, J. Symb. Log. 73 (4), 1097–1121 (2008). DOI: https://doi.org/10.2178/jsl/1230396908
13. А.Б. Хуторецкий, О неглавных нумерациях, Алгебра и логика 8 (6), 726–732 (1969). URL: https://www.mathnet.ru/rus/al1228
14. А.Б. Хуторецкий, О мощности верхней полурешетки вычислимых нумераций, Алгебра и логика 10 (5), 561–569 (1971). URL: https://www.mathnet.ru/rus/al1317
15. M. Kummer, A note on direct sums of Friedbergnumberings, J. Symb. Log. 54 (3), 1009–1010 (1989). DOI: https://doi.org/10.2307/2274760
16. A.H. Lachlan, A note on universal sets, J. Symb. Log. 31 (4), 574–574 (1966). DOI: https://doi.org/10.2307/2269692
17. С.С. Марченков, О вычислимых нумерациях семейств общерекурсивных функций, Алгебра и логика 11 (5), 588–607 (1972). URL: https://www.mathnet.ru/rus/al1353
18. Ш.Д. Нодиров, М.Х. Файзрахманов, Некоторые свойства классов минимальных нумераций семейств арифметических множеств, Матем. и теор. комп. науки 2 (1), 94–108 (2024). DOI: https://doi.org/10.26907/2949-3919.2024.1.94-108
19. С.Ю. Подзоров, О предельности наибольшего элемента полурешетки Роджерса, Матем. тр. 7 (2), 98–108 (2004). URL: https://www.mathnet.ru/rus/mt78
20. С.Ю. Подзоров, Арифметические m-степени, Сиб. матем. журн. 49 (6), 1391–1410 (2008). URL: https://www.mathnet.ru/rus/smj1926
21. M.B. Pour-El, G¨odel numberings versus Friedberg numberings, Proc. AMS 15 (2), 252–256 (1964). DOI: https://doi.org/10.2307/2034045
22. J.S. Royer, A connotational theory of program structure, Springer-Verlag, Berlin, 1987.
23. B. Schinzel, On decomposition of Godelnumberings into Friedbergnumberings, J. Symb. Log. 47 (2), 267–274 (1982). DOI: https://doi.org/10.2307/2273141
24. В.Л. Селиванов, Индексные множества фактор-объектов нумерации Поста, Алгебра и логика 27 (3), 343–358 (1988). URL: https://www.mathnet.ru/rus/al2020
25. V.L. Selivanov, Precomplete numberings, J. Math. Sci. 256 (1), 96–124 (2021). DOI: https://doi.org/10.1007/s10958-021-05422-2
26. R.I. Soare, Turing computability. Theory and applications o computability, Springer-Verlag, Berlin, 2016. DOI: https://doi.org/10.1007/978-3-642-31933-4
27. S.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
Рецензия
Для цитирования:
Файзрахманов М.Х. Вычислимые накрытия арифметических классов программных систем. Математика и теоретические компьютерные науки. 2026;4(1):47-66. https://doi.org/10.26907/2949-3919.2026.1.47-66
For citation:
Faizrahmanov M.Kh. Computable covers for arithmetical collections of programming systems. Mathematics and Theoretical Computer Science. 2026;4(1):47-66. https://doi.org/10.26907/2949-3919.2026.1.47-66
Просмотров:
52
JATS XML
Послать статью по эл. почте 