TY - JOUR

T1 - On Universal Pairs in the Ershov Hierarchy

AU - Bazhenov, N. A.

AU - Mustafa, M.

AU - Ospichev, S. S.

N1 - Funding Information: N. A. Bazhenov and S. S. Ospichev were supported by the Mathematical Center in Akademgorodok (Agreement 075–15–2019–1613 with the Ministry of Science and Higher Education). M. Mustafa was supported by Nazarbayev University Faculty Development Competitive Research Grants N090118FD5342 and partially supported by the MES RK Grant AP08856834. Publisher Copyright: © 2021, Pleiades Publishing, Ltd. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/1

Y1 - 2021/1

N2 - We develop the Ershov theory of C-classes for some finite families of sets in the Ershovhierarchy. We generalize the result by Muchnik on multiple$ m $-reducibility as follows: There exists an $ m $-universal pair of disjoint setsfor each level of the Ershov hierarchy.

AB - We develop the Ershov theory of C-classes for some finite families of sets in the Ershovhierarchy. We generalize the result by Muchnik on multiple$ m $-reducibility as follows: There exists an $ m $-universal pair of disjoint setsfor each level of the Ershov hierarchy.

KW - $ m $-reducibility

KW - 510.55

KW - C-class

KW - computable numbering

KW - Ershov hierarchy

UR - http://www.scopus.com/inward/record.url?scp=85100120285&partnerID=8YFLogxK

U2 - 10.1134/S0037446621010031

DO - 10.1134/S0037446621010031

M3 - Article

AN - SCOPUS:85100120285

VL - 62

SP - 23

EP - 31

JO - Siberian Mathematical Journal

JF - Siberian Mathematical Journal

SN - 0037-4466

IS - 1

ER -