On bounded $m$-reducibilities
Algebra and discrete mathematics, no. 2 (2005), pp. 1-19
Voir la notice de l'article provenant de la source Math-Net.Ru
Conditions for classes ${\mathfrak F}^1,{\mathfrak F}^0$ of non-decreasing total one-place arithmetic functions to define reducibility
$\leq_m[^{{\mathfrak R}^1}_{{\mathfrak R}^0}]\leftrightharpoons\{(A,B)|A,B\subseteq\mathbb N\ \\ (\exists r.f. \ h) (\exists f_1\in{\mathfrak F}^1)(\exists f_0\in{\mathfrak F}^0) $ $[A\le_m^h\,B\ \\ f_0\unlhd h\unlhd f_1]\}$
where $k\unlhd l$ means that function $l$ majors function $k$ almost everywhere are studied. It is proved that the system of these reducibilities is highly ramified, and examples are constructed which differ drastically $\leq_m[^{{\mathfrak R}^1}_{{\mathfrak R}^0}]$ from the standard $m$-reducibility with respect to systems of degrees. Indecomposable and recursive degrees are considered.
Keywords:
bounded reducibilities, degrees of unsolvability, singular reducibility, cylinder, indecomposable degree.
@article{ADM_2005_2_a0,
author = {Vladimir N. Belyaev},
title = {On bounded $m$-reducibilities},
journal = {Algebra and discrete mathematics},
pages = {1--19},
publisher = {mathdoc},
number = {2},
year = {2005},
language = {en},
url = {http://geodesic.mathdoc.fr/item/ADM_2005_2_a0/}
}
Vladimir N. Belyaev. On bounded $m$-reducibilities. Algebra and discrete mathematics, no. 2 (2005), pp. 1-19. http://geodesic.mathdoc.fr/item/ADM_2005_2_a0/