Эквивалентность двух моделей вычислимости в алгебраических системах | Sciact - Система учета научной деятельности ИМ СО РАН

Эквивалентность двух моделей вычислимости в алгебраических системах Научная публикация

Журнал

Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304

Вых. Данные

Год: 2026, Том: 23, Номер: 2, Страницы: 766-778 Страниц : 13

Ключевые слова

обобщенная вычислимость, списочная надстройка, модель Московакиса

Авторы

Карацев Н.Р. ¹ , Рыбалов А.Н. ¹

Организации

1	Омский филиал Института математики им. С.Л.Соболева СО РАН

Информация о финансировании (1)

Российский научный фонд

25-11-20023

В данной работе доказывается эквивалентность вычислимости над списочной надстройкой И.В.Ашаева, В.Я.Беляева и А.Г.Мясникова, и вычислимости по Московакису для классов примитивно вычислимых функций. Частично рекурсивные функции над списочной надстройкой являются однозначными, в то время, как вычислимые функции по Московакису могут быть многозначными (то есть отношениями). Поэтому формально класс частично вычислимых функций над списочной надстройкой, может быть уже класса вычислимых функций по Московакису. В данной статье вводится понятие вычислимого отношения над списочной надстройкой и доказывается, что оно совпадает с понятием отношения, вычислимого по Московакису.

Карацев Н.Р. , Рыбалов А.Н.
Эквивалентность двух моделей вычислимости в алгебраических системах
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2026. Т.23. №2. С.766-778.

Поступила в редакцию:	25 мая 2026 г.
Принята к публикации:	23 июн. 2026 г.
Опубликована в печати:	15 сент. 2026 г.
Опубликована online:	15 сент. 2026 г.

Нет идентификаторов