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

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

Dates:

Submitted:	May 25, 2026
Accepted:	Jun 23, 2026
Published print:	Sep 15, 2026
Published online:	Sep 15, 2026

Identifiers: No identifiers