Обобщенно вычислимые нумерации и неподвижные точки
Аннотация
Доказывается, что для любого в. п. множества W его невычислимость равносильна выполнению теоремы рекурсии (с параметрами) в каждой универсальной W-вычислимой нумерации, а также ее слабой предполноте и неразложимости. Устанавливается, что тьюринговая полнота в. п. оракула W равносильна наличию предполной W-вычислимой нумерации у любого W-вычислимого семейства
Об авторе
М. Х. Файзрахманов
Казанский (Приволжский) федеральный университет,
Научно-образовательный математический центр ПФО
Россия
Россия
ул. Кремлевская, д. 18, г. Казань, 420008
Список литературы
1. С. С. Гончаров, А. Сорби, Обобщенно-вычислимые нумерации и нетривиальные по- лурешетки Роджерса, Алгебра и логика 36 (6), 621–641 (1997). URL: http://mi.mathnet.ru/al2412
2. S. A. Badaev, S. S. Goncharov, The theory of numberings: open problems, Contemporary Math. 257, 23–38 (2000). URL: http://www.ams.org/books/conm/257/
3. С. А. Бадаев, С. С. Гончаров, О полурешетках Роджерса семейств арифметических множеств, Алгебра и логика 40 (5), 507–522 (2001). URL: http://mi.mathnet.ru/al233
4. С.Ю. Подзоров, Начальные сегменты в полурешетках Роджерса Σ0 n-вычислимых нумераций, Алгебра и логика 42 (2), 211–226 (2003). URL: http://mi.mathnet.ru/al233
5. С.Ю. Подзоров, О локальном строении полурешеток Роджерса Σ0 n-вычислимых ну- мераций, Алгебра и логика 44 (2), 148–172 (2005). URL: http://mi.mathnet.ru/al99
6. S. A. Badaev, S. S. Goncharov, Computability and numberings, in: S. B. Cooper (ed.) et al., New computational paradigms. Changing conceptions of what is computable, New York, NY, Springer-Verlag, 19–34 (2008). DOI: https://doi.org/10.1007/978-0-387-68546-5_2
7. М. Х. Файзрахманов, О теореме Хуторецкого для обобщенно вычислимых семейств, Алгебра и логика 58 (4), 528–541 (2019). URL: http://mi.mathnet.ru/al914
8. С. А. Бадаев, С. С. Гончаров, Обобщенно вычислимые универсальные нумерации, Ал- гебра и логика 53 (5), 555–569 (2014). URL: http://mi.mathnet.ru/al650
9. С. А. Бадаев, А. А. Исахов, Некоторые абсолютные свойства A-вычислимых нуме- раций, Алгебра и логика 57 (4), 426–447 (2018). URL: http://mi.mathnet.ru/al857
10. М. Х. Файзрахманов, О полурешетках Роджерса обобщенно вычислимых нумераций, Сиб. матем. журн. 58 (6), 1418–1427 (2017). URL: http://mi.mathnet.ru/smj2948
11. S. A. Badaev, S. S. Goncharov, A. Sorbi, Completeness and universality of arithmetical numberings, in: Computability and Models, Univ. Ser. Math., Kluwer/Plenum, New York, 11–44 (2003). DOI: https://doi.org/10.1007/978-1-4615-0755-0_2
12. С.Ю. Подзоров, О предельности наибольшего элемента полурешетки Роджерса, Матем. тр. 7 (2), 98–108 (2004). URL: http://mi.mathnet.ru/mt78
13. Ю.Л. Ершов, О неотделимых парах, Алгебра и логика 9 (6), 661–666 (1970). URL: http://mi.mathnet.ru/al1272
14. В. Л. Селиванов, Предполные нумерации и функции без неподвижных точек, Матем. заметки 51 (1), 149–155 (1992). URL: http://mi.mathnet.ru/mz4463
15. В. Л. Селиванов, Предполные нумерации, Итоги науки и техн. Сер. Соврем. матем. и ее прил. Темат. обз. 157, 106–134 (2018). URL: http://mi.mathnet.ru/into409
16. H. Barendregt, S. A. Terwijn, Fixed point theorems for precomplete numberings, Ann. Pure App. Logic 170 (10), 1151–1161 (2019). DOI: https://doi.org/10.1016/j.apal.2019.04.013
17. Т. Н. Payne, Effective extandability and fixed points, Notre Dame J. Form. Log. 14 (1), 123–124 (1973). DOI: https://doi.org/10.1305/ndjfl/1093890819
18. С. А. Бадаев, О слабо предполных позитивных эквивалентностях, Сиб. матем. журн. 32 (2), 166–169 (1991). URL: http://mi.mathnet.ru/smj4620
19. Ю.Л. Ершов, Теория нумераций, Наука, М., 1977.
20. 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
21. R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in mathematical logic. Springer-Verlag, Berlin, Heidelberg, New York, etc., 1987. URL: https://link.springer.com/book/9783540666813
22. M. Kh. Faizrahmanov, Extremal numberings and fixed point theorems, Math. Log. Q. 68 (4), 398–408 (2022). DOI: https://doi.org/10.1002/malq.202200035
23. М. Х. Файзрахманов, Универсальные обобщенно вычислимые нумерации и гиперим мунность, Алгебра и логика 56 (4), 506–521 (2017). URL: http://mi.mathnet.ru/al811
Рецензия
Для цитирования:
Файзрахманов М.Х. Обобщенно вычислимые нумерации и неподвижные точки. Математика и теоретические компьютерные науки. 2023;1(2):35-49.
For citation:
Faizrahmanov M.Kh. Generalized computable numberings and fixed points. Mathematics and Theoretical Computer Science. 2023;1(2):35-49. (In Russ.)
Просмотров:
139
Послать статью по эл. почте 