|сгенерировать QR код
Открытый доступ
Только для подписчиков
О бесконечных прямых суммах минимальных нумераций функциональных семейств
https://doi.org/10.26907/0021-3446-2025-4-38-52
Аннотация
В статье рассматриваются два подхода к определению вычислимости нумераций семейств всюду определенных функций. Рассматривается как классическое определение вычислимой нумерации семейства вычислимых функций, согласно которому по номеру функции в этой нумерации эффективно определяется ее геделевский номер, так и расширяющее предыдущее определение, основанное на равномерном применении понятия вычислимо перечислимого слева элемента бэровского пространства. Основной вопрос, исследуемый в статье, заключается в возможности порождения всех вычислимых нумераций семейства замыканием относительно сводимости бесконечных прямых сумм равномерных последовательностей его однозначных, позитивных и минимальных нумераций.
Ключевые слова
При поддержке: Работа поддержана грантом Российского научного фонда (проект 23-21-00181) и выполнена в рамках реализации программы развития Научно-образовательного математического центра Приволжского федерального округа (соглашение 075-02-2023-944)
Об авторах
Ш. Д. Нодиров
Каршинский государственный университет
Узбекистан
Узбекистан
Шохрух Дилмуродович Нодиров
Ул. Кучабог, д. 17, Карши, 180100
М. Х. Файзрахманов
Казанский федеральный университет
Узбекистан
Узбекистан
Марат Хайдарович Файзрахманов
Ул. Кучабог, д. 17, Карши, 180100
З. К. Щедрикова
Университет Иннополис
Россия
Россия
Злата Константиновна Щедрикова
Ул. Университетская, д. 1, Иннополис, 420500
Список литературы
1. Friedberg R. Three theorems on recursive enumeration, J. Symb. Log. 23 (3), 309–316 (1958).
2. Schinzel B. On decomposition of Go¨delnumberings into Friedbergnumberings, J. Symb. Log. 47 (2), 267–274 (1982).
3. Ершов Ю.Л. Нумерации семейств общерекурсивных функций, Сиб. матем. журн. 8 (5), 1015–1025 (1967).
4. Марченков С.С. О вычислимых нумерациях семейств общерекурсивных функций, Алгебра и логика 11 (5), 588–607 (1972).
5. Downey R.G., Hirschfeldt D.R. Algorithmic Randomness and Complexity, Theory Appl. Comput. (Springer, New York, 2010).
6. Kjos-Hanssen B., Stephan F., Teutsch J. Arithmetic complexity via effective names for random sequences, ACM Trans. Comput. Log. 13 (3), 1–18 (2012).
7. Stephan F., Teutsch J. Things that can be made into themselves, Information and Computation 237, 174–186 (2014).
8. Soare R.I. Recursively enumerable sets and degrees. A study of computable functions and computably generated sets (Perspect. Math. Log., Omega Series), Springer-Verlag, Berlin etc., 1987.
9. Ершов Ю.Л. Теория нумераций (Наука, М., 1977).
10. Ershov Yu.L. Theory of numberings, in: Handbook of Computability Theory, 140, Stud. Logic Found. Math., ed. by Griffor E.R. (Elsevier, Amsterdam, 1999).
11. Brodhead P., Kjos-Hanssen B., Numberings and randomness, in: Mathematical Theory and Computational practice. CiE 2009, V. 5635, Lecture Notes in Computer Science ed. by K. Ambos-Spies, B. Lo¨we, W. Merkle (Springer, Berlin, Heidelberg, 2009).
12. Faizrahmanov M., Kalimullin I. Limitwise monotonic sets of reals, Math. Log. Quart. 61 (3), 224–229 (2015).
13. Herbert I., Jain S., Mustafa M., Lempp S., Stephan F. Reductions between types of numbering, Ann. Pure. App. Log. 170 (12), 102716 (2019).
14. Бадаев С.А. О позитивных нумерациях, Сиб. матем. журн. 18 (3), 483–496 (1977).
15. Faizrahmanov M., Shchedrikova Z. Effectively infinite classes of numberings and computable families of reals, Comput. 12 (4), 339–350 (2023).
Рецензия
Для цитирования:
Нодиров Ш.Д., Файзрахманов М.Х., Щедрикова З.К. О бесконечных прямых суммах минимальных нумераций функциональных семейств. Известия высших учебных заведений. Математика. 2025;(4):38-52. https://doi.org/10.26907/0021-3446-2025-4-38-52
For citation:
Nodirov Sh.D., Faizrahmanov M.Kh., Shchedrikova Z.K. On infinite direct sums of minimal numberings of functional families. Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika. 2025;(4):38-52. (In Russ.) https://doi.org/10.26907/0021-3446-2025-4-38-52
Просмотров:
29
Послать статью по эл. почте 