RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский математический журнал // Архив

Сиб. матем. журн., 2018, том 59, номер 4, страницы 823–833 (Mi smj3012)

Эта публикация цитируется в 4 статьях

Позитивные представления семейств относительно $e$-оракулов

И. Ш. Калимуллинa, В. Г. Пузаренкоb, М. Х. Файзрахмановa

a Казанский (Приволжский) федеральный университет, ул. Кремлевская, 18, Казань 420008
b Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090

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

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

УДК: 510.5

MSC: 35R30

Статья поступила: 24.09.2017

DOI: 10.17377/smzh.2018.59.407


 Англоязычная версия: Siberian Mathematical Journal, 2018, 59:4, 648–656

Реферативные базы данных:


© МИАН, 2024