Нумерации в допустимых множествах над эквивалентностями
Аннотация
Строится серия примеров допустимых множеств A, в которых семейство всех A-в.п. множеств не имеет ни негативной, ни позитивной вычислимых A-нумераций.
Ключевые слова
нумерация,
разрешимая нумерация,
позитивная нумерация,
негативная нумерация,
вычислимая нумерация,
допустимое множество
При поддержке: Работа И.Ш. Калимуллина поддержана грантом Российского научного фонда (проект № 23-21-00181) и выполнена в рамках реализации программы развития Научно-образовательного математического центра Приволжского федерального округа (соглашение № 075-02-2023-944). Работа В.Г. Пузаренко поддержана проектом FWNF-2022-0012 (Классификационные вопросы синтаксиса и семантики логических систем).
Об авторах
И. Ш. Калимуллин
Казанский (Приволжский) федеральный университет, Научно-образовательный математический центр ПФО
Россия
Россия
Калимуллин Искандер Шагитович
ул. Кремлевская, д. 18, г. Казань, 420008
В. Г. Пузаренко
Институт математики им. С.Л. Соболева СО РАН; Новосибирский Государственный Университет
Россия
Россия
Пузаренко Вадим Григорьевич
пр. Акад. Коптюга, д. 4, г. Новосибирск, 630090, e-mail: vagrig@math.nsc.ru
ул. Пирогова, д. 1, г. Новосибирск, 630090
Список литературы
1. R.M. Friedberg, Three theorems on recursive enumeration. I: Decomposition. II: Maximal set. III: Enumeration without duplication, J. Symbolic Logic, 23 (3), 309–316 (1958), DOI: https://doi.org/10.2307/2964290.
2. В.Г. Пузаренко, О разрешимых вычислимых A-нумерациях, Алгебра и логика 41 (5), 568–584 (2002). URL: https://www.mathnet.ru/rus/al197
3. В.Г. Пузаренко, К вычислимости на специальных моделях, Сиб. матем. журн. 46 (1), 185–208 (2005). URL: https://www.mathnet.ru/rus/smj951
4. И.Ш. Калимуллин, В.Г. Пузаренко, М.Х. Файзрахманов, Позитивные нумерации в допустимых множествах, Сиб. матем. журн. 61 (3), 607–621 (2020). DOI: https://doi.org/10.33048/smzh.2020.61.309.
5. Ю.Л. Ершов, Определимость и вычислимость, Научн. кн., Новосибирск, 1996.
6. Ю.Л. Ершов, Теория нумераций, Наука, М., 1977.
7. J. Barwise, Admissible sets and structures, Springer, 1975.
8. Р.И. Соар, Вычислимо перечислимые множества и степени, Изд-во Казан. матем. о-ва, Казань, 2000.
9. Ю.Л. Ершов, Проблемы разрешимости и конструктивные модели, Наука, М., 1980.
10. С.С. Гончаров, Ю.Л. Ершов, Конструктивные модели, Научн. кн., Новосибирск, 1999.
11. В.Г. Пузаренко, Обобщенные нумерации и определимость поля R в допустимых множествах, Вестн. НГУ: сер. матем. мех., инф. 3 (2), 107–117 (2003).
12. В.Г. Пузаренко, О вычислимости над моделями разрешимых теорий, Алгебра и логика 39 (2), 170–197 (2000). URL: https://www.mathnet.ru/rus/al272
13. Yu.L. Ershov, V.G. Puzarenko, A.I. Stukachev, HF-Computability, Computability in Context: Computation and Logic in the Real World (ed. S Barry Cooper and Andrea Sorbi), 169–242 (2011). DOI: https://doi.org/10.1142/p577.
Рецензия
Для цитирования:
Калимуллин И.Ш., Пузаренко В.Г. Нумерации в допустимых множествах над эквивалентностями. Математика и теоретические компьютерные науки. 2023;1(3):33-45.
For citation:
Kalimullin I.Sh., Puzarenko V.G. Numberings in the admissible sets over equivalence relations. Mathematics and Theoretical Computer Science. 2023;1(3):33-45. (In Russ.)
Просмотров:
128
Послать статью по эл. почте 