Two theorems on many-one degrees of recursively enumerable sets
Algebra i logika, Tome 11 (1972) no. 2, pp. 216-229
Citer cet article
Voir la notice de l'article provenant de la source Math-Net.Ru
Teоpeмa 1. Каждая нерекурсивная рекурсивно перечислимая тьюрингова степень содержит минимальную рекурсивно перечислимую $m$-степень. Теорема 2. Над каждой некреативной рекурсивно перечислимой $m$-степенью $a$ находится рекурсивно перечислимая $m$-степень такая, что для любой $m$-степени $c выполняется соотношение $c\leqslant b$.