Калимуллин И. Ш., Пузаренко В. Г., Файзрахманов М. Х.
Позитивные представления семейств относительно $e$-оракулов

Вводится понятие $A$-нумерации, которое служит обобщением классического понятия нумерации. На рассматриваемые объекты переносятся все понятия, введенные для обычных нумераций, и исследуется проблема существования позитивных и разрешимых вычислимых $A$-нумераций для естественных семейств множеств, $e$-сводящихся к фиксированному множеству. Доказано, что любое семейство с наибольшим по включению множеством, имеющее вычислимую $A$-нумерацию, имеет и позитивную вычислимую $A$-нумерацию. Кроме того, для определенных семейств строится разрешимая (даже однозначная) вычислимая всюду определенная $A$-нумерация в случае, когда $A$ — низкое множество; рассматривается также релятивизация, содержащая случаи всех тотальных множеств (которые фактически соответствуют вычислимости с обычным оракулом).

I. Sh. Kalimullin, V. G. Puzarenko, M. Kh. Faizrahmanov
Positive Presentations of Families Relative to $e$-Oracles

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).

DOI 10.17377/smzh.2018.59.407
Ключевые слова: нумерация, разрешимая нумерация, позитивная нумерация, вычислимая нумерация, вычислимое множество, вычислимо перечислимое множество, $e$-сводимость.

Свободный доступ к полным текстам предоставляется после 1 июля года, следующего за годом публикации