Дегтев А. Н., Сакунова Е. С.
О сводимостях частично рекурсивных функций
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:

• PDF file (319 KB)
• PostScript file (610 KB)