RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 1972 Volume 11, Number 2, Pages 216–229 (Mi al1336)

This article is cited in 4 papers

Two theorems on many-one degrees of recursively enumerable sets

A. H. Lachlan


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

UDC: 517.11:518.5

Received: 23.02.1972

Language: English



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024