Некоторые свойства классов минимальных нумераций семейств арифметических множеств
https://doi.org/10.26907/2949-3919.2024.1.94-108
Аннотация
Доказано, что для каждого u ⩾ 2 класс всех однозначных Σ0 uвычислимых нумераций любого бесконечного семейства всюду определенных функций эффективно бесконечен и класс всех его Σ0 u-1-вычислимых нумераций порождается замыканием вниз относительно сводимости множества всех бесконечных прямых сумм равномерно Σ0 u-1-вычислимых последовательностей его однозначных нумераций. Установлено, что если u > 2, то класс всех Σ0 u-вычислимых нумераций любого бесконечного семейства порождается бесконечными прямыми суммами равномерно Σ0 u-вычислимых и равномерно Σ0 uминимальных последовательностей его нумераций.
Об авторах
Ш. Д. Нодиров
Каршинский государственный университет
Узбекистан
Узбекистан
Шохрух Дилмуродович Нодиров
ул. Кучабаг, д. 17, г. Карши, 180119
М. Х. Файзрахманов
Казанский (Приволжский) федеральный университет, Научно-образовательный математический центр ПФО
Россия
Россия
Марат Хайдарович Файзрахманов
ул. Кремлевская, д. 18, г. Казань, 420008
Список литературы
1. Ю.Л. Ершов, Теория нумераций, Наука, М., 1977.
2. 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
3. Ю.Л. Ершов, Определимость и вычислимость (Сибирская школа алгебры и логики), Новосибирск, Науч. кн., М., Экономика, 2-е изд., испр. и доп., 2000.
4. С.С. Гончаров, А. Сорби, Обобщенно-вычислимые нумерации и нетривиальные полурешетки Роджерса, Алгебра и логика 36 (6), 621–641 (1997). URL: http://mi.mathnet.ru/al2412
5. С.А. Бадаев, С.С. Гончаров, О полурешетках Роджерса семейств арифметических множеств, Алгебра и логика 40 (5), 507–522 (2001). URL: http://mi.mathnet.ru/al233
6. С.Ю. Подзоров, О локальном строении полурешёток Роджерса Σ0 n-вычислимых нумераций, Алгебра и логика 44 (2), 148–172 (2005). URL: http://mi.mathnet.ru/al99
7. С.А. Бадаев, С.С. Гончаров, А. Сорби, Типы изоморфизмов полурешёток Роджерса семейств из различных уровней арифметической иерархии, Алгебра и логика 45 (6), 637–654 (2006). URL: http://www.mathnet.ru/rus/al163
8. 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, Springer-Verlag, 19–34 (2008). DOI: https://doi.org/10.1007/978-0-387-68546-5_2
9. М.Х. Файзрахманов, О теореме Хуторецкого для обобщённо вычислимых семейств, Алгебра и логика 58 (4), 528–541 (2019). DOI: https://doi.org/10.33048/alglog.2019.58.408
10. С.А. Бадаев, Минимальные нумерации, Тр. Ин-та математики СО РАН 25, 3–34 (1993). URL: https://www.mathnet.ru/rus/mt425
11. М.Х. Файзрахманов, Минимальные обобщенно вычислимые нумерации и высокие степени, Сиб. матем. журн. 58 (3), 710–716 (2017). DOI: https://doi.org/10.17377/smzh.2017.58.318
12. С.А. Бадаев, Об одной проблеме С.С. Гончарова, Сиб. матем. журн. 32 (3), 212–214 (1991). URL: https://www.mathnet.ru/rus/smj3338
13. S.S. Goncharov, A. Yakhnis, V. Yakhnis, Some effectively infinite classes of enumerations, Ann. Pure App. Log. 60 (3), 207–235 (1993). DOI: https://doi.org/10.1016/0168-0072(93)90076-P
14. B. Schinzel, On decomposition of G¨odelnumberings into Friedbergnumberings, J. Symb. Log. 47 (2), 267–274 (1982). DOI: https://doi.org/10.2307/2273141
15. B. Schinzel, Complexity of decompositions of G¨odel numberings, Fundam. Inform. 5 (1), 15–33 (1982). DOI: https://doi.org/10.3233/FI-1982-5103
16. 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
17. J. Myhill, Creative sets, Z. Math. Logik und Grundlag. Math. 1 (2), 97–108 (1955). DOI: https://doi.org/10.1002/malq.19550010205
18. M.Kh. Faizrahmanov, Z. K. Shchedrikova, Effectively infinite classes of numberings and computable families of feals, Computability 12 (4), 339–350 (2023). DOI: https://doi.org/10.3233/COM-230461
19. 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
20. M. Faizrahmanov, Fixed point theorems for minimal numberings, J. Log. Comput. (2023) DOI: https://doi.org/10.1093/logcom/exad074
21. M. Faizrahmanov, I. Kalimullin, The enumeration spectrum hierarchy of n-families, Math. Log. Quart. 64 (4–5), 420–426 (2016). DOI: https://doi.org/10.1002/malq.201500056
Рецензия
Для цитирования:
Нодиров Ш.Д., Файзрахманов М.Х. Некоторые свойства классов минимальных нумераций семейств арифметических множеств. Математика и теоретические компьютерные науки. 2024;2(1):94-108. https://doi.org/10.26907/2949-3919.2024.1.94-108
For citation:
Nodirov Sh.D., Faizrahmanov M.Kh. Some properties of classes of minimal numberings of arithmetical set families. Mathematics and Theoretical Computer Science. 2024;2(1):94-108. (In Russ.) https://doi.org/10.26907/2949-3919.2024.1.94-108
Просмотров:
264
Послать статью по эл. почте 