СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ

АННОТАЦИИ

Рассматриваются $m$-, $p$- и $e$-сводимости частично-рекурсивных функций
(ЧРФ).
Доказывается, что верхняя полурешетка
$L$
$e$-степеней ЧРФ изоморфна прямому произведению верхней полурешетки
$T$-степеней на полурешетку рекурсивно-перечислимых множеств (РПМ).
Вводятся две сводимости попарно не пересекающихся $n$-ок РПМ и
показывается, что при
$n\ge2$
$p$-сводимость строго сильнее их
$mp$-сводимости. Доказывается, что
$\operatorname{Th}(L_p^s)\ne \operatorname{Th}(L_p^t)$
при
$s\ne t$,
где
$L_p^n$~--- верхняя полурешетка
$n$-ок РПМ относительно
$p$-сводимости. Библиогр.~5.