Дегтев А. Н., Сакунова Е. С.
О сводимостях частично рекурсивных функций
Degtev A. N., Sakunova E. S.
On reducibility of partial recursive functions
Рассматриваются $m$-, $p$- и $e$-сводимости частично-рекурсивных функций
(ЧРФ). Доказывается, что верхняя полурешетка $L$ $e$-степеней ЧРФ изоморфна
прямому произведению верхней полурешетки $T$-степеней на полурешетку
рекурсивно-перечислимых множеств (РПМ). Вводятся две сводимости попарно
не пересекающихся $n$-ок РПМ и показывается, что при $n\ge2$ $p$-сводимость
строго сильнее их $mp$-сводимости. Доказывается, что ${Th}(L_p^s)\ne
{Th}(L_p^t)$ при $s\ne t$, где $L_p^n$ --- верхняя полурешетка $n$-ок
РПМ относительно $p$-сводимости.
Полный текст статьи / Full texts:
|