|
Algebra and Discrete Mathematics, 2005, выпуск 2, страницы 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
Аннотация:
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.
Ключевые слова:
bounded reducibilities, degrees of unsolvability, singular reducibility, cylinder, indecomposable degree.
Поступила в редакцию: 11.04.2005 Исправленный вариант: 04.07.2005
Образец цитирования:
Vladimir N. Belyaev, “On bounded $m$-reducibilities”, Algebra Discrete Math., 2005, no. 2, 1–19
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/adm299 https://www.mathnet.ru/rus/adm/y2005/i2/p1
|
Статистика просмотров: |
Страница аннотации: | 99 | PDF полного текста: | 43 | Первая страница: | 1 |
|