Geodesic
$eT$-reducibility of sets
Modelirovanie i analiz informacionnyh sistem, Tome 26 (2019) no. 2, pp. 306-311 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{MAIS_2019_26_2_a9,
     author = {R. R. Iarullin},
     title = {$eT$-reducibility of sets},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {306--311},
     year = {2019},
     volume = {26},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2019_26_2_a9/}
}
TY  - JOUR
AU  - R. R. Iarullin
TI  - $eT$-reducibility of sets
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2019
SP  - 306
EP  - 311
VL  - 26
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MAIS_2019_26_2_a9/
LA  - ru
ID  - MAIS_2019_26_2_a9
ER  - 
%0 Journal Article
%A R. R. Iarullin
%T $eT$-reducibility of sets
%J Modelirovanie i analiz informacionnyh sistem
%D 2019
%P 306-311
%V 26
%N 2
%U http://geodesic.mathdoc.fr/item/MAIS_2019_26_2_a9/
%G ru
%F MAIS_2019_26_2_a9
R. R. Iarullin. $eT$-reducibility of sets. Modelirovanie i analiz informacionnyh sistem, Tome 26 (2019) no. 2, pp. 306-311. http://geodesic.mathdoc.fr/item/MAIS_2019_26_2_a9/

[1] Rogers H., Theory of Recursive Functions and Effective Computability, The MIT Press, 1987 | MR

[2] Soare Robert I., Recursively Enumerable Sets and Degrees, Springer, 1999 | MR

[3] Hodzhayanc M. YU., “O strukture $e$-stepenej”, Izvestiya AN ArSSR “Matematika”, XV:3 (1980), 165–175 | MR | Zbl

[4] Polyakov E. A., Rozinas M. G., Teoriya algoritmov, IVGU, Ivanovo, 1976

[5] Kleene S. C., Post E. L., “The upper semi-lattice of degrees of recursive unsolvability”, Annals of Mathematics, 59 (1954), 379–407 | DOI | MR | Zbl

[6] Case J., “Enumeration reducibility and partial degrees”, Annals of Mathematical Logic, 2:4 (1971), 419–439 | DOI | MR | Zbl

[7] Rozinas M. G., Operaciya skachka dlya nekotoryh vidov svodimosti, VINITI Dep. 3185-76

[8] Medvedev Yu. T., “Stepeni trudnosti massovyh problem”, Dokl. AN SSSR, 104 (1955), 501–504 | Zbl

[9] Hodzhayanc M. Yu., “$e$-stepeni, $T$-stepeni i aksiomaticheskie teorii”, DAN ArSSR, 73:2 (1981), 73–77 | MR | Zbl

[10] Solon B. YA., “O sootnoshenie mezhdu $e$-stepenyami i $T$-stepenyami”, Izvestiya vuzov, “Matematika”, 3 (1995), 51–61 | MR | Zbl