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

Алгебра и логика, 1972, том 11, номер 2, страницы 216–229 (Mi al1336)

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

Two theorems on many-one degrees of recursively enumerable sets

A. H. Lachlan


Аннотация: Teоpeмa 1. Каждая нерекурсивная рекурсивно перечислимая тьюрингова степень содержит минимальную рекурсивно перечислимую $m$-степень.
Теорема 2. Над каждой некреативной рекурсивно перечислимой $m$-степенью $a$ находится рекурсивно перечислимая $m$-степень такая, что для любой $m$-степени $c<a$ выполняется соотношение $c\leqslant b$.

УДК: 517.11:518.5

Поступило: 23.02.1972

Язык публикации: английский



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


© МИАН, 2024