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

Алгебра и логика, 1979, том 18, номер 4, страницы 415–425 (Mi al1656)

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

Г. Н. Кобзев


Аннотация: Для всякого рекурсивно-перечислимого (р.п.) множества $A$ полной тьюринговой степени указывается р.п. множество $B$, $B\leqslant_{tt}A$, имеющее ретрассируемое сильно равномерно гипериммунное дополнение. Табличная степень является минимальным элементом полурешетки р.п. $tt$-степеней, если и только если она содержит р.п. полурекурсивное множество минимальной $m$-степени. Для всякой р.п. тьюринговой степени $a\ne0$ строится тьюрингова степень $b$, $0<b\leqslant a$, не содержащая $\eta$-максимальных полурекурсивных множеств.

УДК: 518.5

Поступило: 29.11.1978



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


© МИАН, 2024