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


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


Адрес редакции:
пр. Коптюга, 4,
Новосибирск 630090.
Телефон: (383-2) 333-493
E-mail: smz@math.nsc.ru