RUS  ENG
Полная версия
ЖУРНАЛЫ // Algebra and Discrete Mathematics // Архив

Algebra Discrete Math., 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.

MSC: 03D20, 03D25, 03D30

Поступила в редакцию: 11.04.2005
Исправленный вариант: 04.07.2005

Язык публикации: английский



Реферативные базы данных:


© МИАН, 2024