|
Algorithms
$eT$-reducibility of sets
R. R. Iarullin Ivanovo State University,
99 Ermaka str., Ivanovo, 153025 Russia
Abstract:
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 $\mathbf{D_ {eT}}$ 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.
Keywords:
eT-reducibility, eT-degrees, eT-jump.
Received: 20.12.2018 Revised: 15.05.2019 Accepted: 17.05.2019
Citation:
R. R. Iarullin, “$eT$-reducibility of sets”, Model. Anal. Inform. Sist., 26:2 (2019), 306–311
Linking options:
https://www.mathnet.ru/eng/mais681 https://www.mathnet.ru/eng/mais/v26/i2/p306
|
|