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...
Saved in:
| 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 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849401169058725888 |
|---|---|
| author | Roman R. Iarullin |
| author_facet | Roman R. Iarullin |
| author_sort | Roman R. Iarullin |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-6d47e9ca0cb44cac9e14d9e7124f48d3 |
| institution | Kabale University |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2019-06-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-6d47e9ca0cb44cac9e14d9e7124f48d32025-08-20T03:37:50ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172019-06-0126230631110.18255/1818-1015-2019-2-306-311911eT -reducibility of SetsRoman R. Iarullin0Ivanovo State UniversityThis 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.https://www.mais-journal.ru/jour/article/view/1220et-reducibilityet-degreeset-jump |
| spellingShingle | Roman R. Iarullin eT -reducibility of Sets Моделирование и анализ информационных систем et-reducibility et-degrees et-jump |
| title | eT -reducibility of Sets |
| title_full | eT -reducibility of Sets |
| title_fullStr | eT -reducibility of Sets |
| title_full_unstemmed | eT -reducibility of Sets |
| title_short | eT -reducibility of Sets |
| title_sort | et reducibility of sets |
| topic | et-reducibility et-degrees et-jump |
| url | https://www.mais-journal.ru/jour/article/view/1220 |
| work_keys_str_mv | AT romanriarullin etreducibilityofsets |