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

Сиб. матем. журн., 1973, том 14, номер 2, страницы 421–426 (Mi smj6076)

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

Отдел заметок

О степенях рекурсивно перечислимых множеств

С. Каллибеков


Аннотация: Пусть через $\mathbf{r}$ обозначена одна из сводимостей: $1$-, $\mathbf{m}$- , табличная, тьюринговая. Доказано существование $\mathbf{r}$-независимой вычислимой последовательности рекурсивно перечислимых множеств $\{B_k\}_{k\in N}$ такой, что каждому $B_k$ $1$-сводится данное $\mathbf{r}$-неполное рекурсивно перечислимое множество $A$. В конце отмечены некоторые следствия, относящиеся к верхней полурешетке $\mathbf{r}$-степеней рекурсивно перечислимых множеств.

УДК: 518.5

Статья поступила: 03.01.1972


 Англоязычная версия: Siberian Mathematical Journal, 1973, 14:2, 290–293

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


© МИАН, 2024