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.

UDC: 510.5

Received: 20.12.2018
Revised: 15.05.2019
Accepted: 17.05.2019

DOI: 10.18255/1818-1015-306-311