RUS  ENG
Полная версия
ЖУРНАЛЫ // Математический сборник // Архив

Матем. сб., 1978, том 106(148), номер 4(8), страницы 507–514 (Mi sm2595)

Эта публикация цитируется в 9 статьях

О $tt$-степенях рекурсивно-перечислимых тьюринговых степеней

Г. Н. Кобзев


Аннотация: Основной результат: если $A$ – полурекурсивное $\eta$-гипергиперпростое множество, то для всякого множества $B$, $A\equiv_TB$, существует нерекурсивное множество $C$, $C\leqslant_mA$ и $C\leqslant_{tt}B$. Если $B$ р. п., то $C\leqslant_qB$. Следствие: если $tt$-степень содержит полурекурсивное $\eta$-максимальное множество, то она является минимальным элементом полурешетки всех $tt$-степеней.
Библиография: 9 названий.

УДК: 518.5

MSC: Primary 03D30, 03D50, 03D25; Secondary 03D55

Поступила в редакцию: 31.05.1977


 Англоязычная версия: Mathematics of the USSR-Sbornik, 1979, 35:2, 173–180

Реферативные базы данных:


© МИАН, 2024