Эта публикация цитируется в
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