eT -reducibility of Sets
This paper is dedicated to the study of eT -reducibility — the most common in the intuitive sense of algorithmic reducibility, which is both enumeration reducibility and decidable one. The corresponding structure of degrees — upper semilattice of eT -degrees is considered. It is shown that it is pos...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2019-06-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1220 |
| Summary: | This paper is dedicated to the study of eT -reducibility — the most common in the intuitive sense of algorithmic reducibility, which is both enumeration reducibility and decidable one. The corresponding structure of degrees — upper semilattice of eT -degrees is considered. It is shown that it is possible to correctly define the jump operation on it by using the T-jump or e-jump of sets. The local properties of eT -degrees are considered: totality and computably enumerable. It is proved that all degrees between the smallest element and the first jump in DeT are computably enumerable, moreover, these degrees contain computably enumerable sets and only them. The existence of non-total eT -degrees is established. On the basis of it, some results have been obtained on the relations between, in particular, from the fact that every eT -degree is either completely contained in some T -or e-degrees, or completely coincides with it, it follows that non-total e-degrees contained in the T-degrees, located above the second T -jump, coincide with the corresponding non-total eT -degrees. |
|---|---|
| ISSN: | 1818-1015 2313-5417 |