On universal pairs in the Ershov hierarchy

2021 
We develop the Ershov theory of C-classes for some finite families of sets in the Ershov hierarchy. We generalize the result by Muchnik on multiple $ m $ -reducibility as follows: There exists an $ m $ -universal pair of disjoint sets for each level of the Ershov hierarchy.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    34
    References
    0
    Citations
    NaN
    KQI
    []