$eT$-reducibility of sets

R. R. Iarullin

Modelirovanie i analiz informacionnyh sistem, Tome 26 (2019) no. 2, pp. 306-311

Résumé

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.

Détail

Keywords: eT-reducibility, eT-degrees, eT-jump.