|
This article is cited in 4 scientific papers (total 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$.
Received: 23.02.1972
Citation:
A. H. Lachlan, “Two theorems on many-one degrees of recursively enumerable sets”, Algebra Logika, 11:2 (1972), 216–229
Linking options:
https://www.mathnet.ru/eng/al1336 https://www.mathnet.ru/eng/al/v11/i2/p216
|
Statistics & downloads: |
Abstract page: | 66 | Full-text PDF : | 50 |
|