Positive Presentations of Families Relative to e-Oracles

Positive Presentations of Families Relative to e-Oracles Full article

Journal

Siberian Mathematical Journal
ISSN: 0037-4466 , E-ISSN: 1573-9260

Output data

Year: 2018, Volume: 59, Number: 4, Pages: 648-656 Pages count : 9 DOI: 10.1134/S0037446618040079

Tags

нумерация, разрешимая нумерация, позитивная нумерация, вычислимая нумерация, вычислимое множество, вычислимо перечислимое множество, e-сводимость.

Authors

Kalimullin I.Sh. ² , Puzarenko V.G. ¹ , Faizrahmanov M.Kh. ²

Affiliations

1	Sobolev Institute of Mathematics
2	Kazan Federal University

We introduce the notion of A-numbering which generalizes the classical notion of numbering. All main attributes of classical numberings are carried over to the objects considered here. The problem is investigated of the existence of positive and decidable computable A-numberings for the natural families of sets e-reducible to a fixed set. We prove that, for every computable A-family containing an inclusion-greatest set, there also exists a positive computable A-numbering. Furthermore, for certain families we construct a decidable (and even single-valued) computable total A-numbering when A is a low set; we also consider a relativization containing all cases of total sets (this in fact corresponds to computability with a usual oracle).

Kalimullin I.S. , Puzarenko V.G. , Faizrahmanov M.K.
Positive Presentations of Families Relative to e-Oracles
Siberian Mathematical Journal. 2018. V.59. N4. P.648-656. DOI: 10.1134/S0037446618040079 WOS Scopus OpenAlex

Калимуллин И.Ш. , Пузаренко В.Г. , Файзрахманов М.Х.
Позитивные представления семейств относительно e-оракулов
Сибирский математический журнал. 2018. Т.59. №4. С.823-833. DOI: 10.17377/smzh.2018.59.407

Web of science:	WOS:000443717700007
Scopus:	2-s2.0-85053006749
OpenAlex:	W2889607482

DB	Citing
Scopus	4
OpenAlex	4
Web of science	4