|
Алгебра и логика, 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$-максимальных полурекурсивных множеств.
Поступило: 29.11.1978
Образец цитирования:
Г. Н. Кобзев, “О $tt$-степенях рекурсивно-перечислимых тьюринговых степеней. II”, Алгебра и логика, 18:4 (1979), 415–425
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al1656 https://www.mathnet.ru/rus/al/v18/i4/p415
|
Статистика просмотров: |
Страница аннотации: | 61 | PDF полного текста: | 26 |
|