On Universal Pairs in the Ershov Hierarchy

N. A. Bazhenov, M. Mustafa, S. S. Ospichev

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)23-31
Number of pages9
JournalSiberian Mathematical Journal
Volume62
Issue number1
DOIs
Publication statusPublished - Jan 2021

Keywords

  • $ m $-reducibility
  • 510.55
  • C-class
  • computable numbering
  • Ershov hierarchy

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'On Universal Pairs in the Ershov Hierarchy'. Together they form a unique fingerprint.

Cite this