|
Algebra and Discrete Mathematics, 2005, Issue 2, Pages 1–19
(Mi adm299)
|
|
|
|
RESEARCH ARTICLE
On bounded $m$-reducibilities
Vladimir N. Belyaev Department of Computer Algebra and
Discrete Mathematics, Odessa National
University, Dvoranskaja st. 2, Odessa,
Ukraine, 65026
Abstract:
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.
Received: 11.04.2005 Revised: 04.07.2005
Citation:
Vladimir N. Belyaev, “On bounded $m$-reducibilities”, Algebra Discrete Math., 2005, no. 2, 1–19
Linking options:
https://www.mathnet.ru/eng/adm299 https://www.mathnet.ru/eng/adm/y2005/i2/p1
|
Statistics & downloads: |
Abstract page: | 93 | Full-text PDF : | 43 | First page: | 1 |
|