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

Сиб. матем. журн., 2017, том 58, номер 2, страницы 365–374 (Mi smj2865)

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

Об одной сводимости и экзистенциальной интерпретируемости структур

А. С. Морозовab

a Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090
b Новосибирский гос. университет, ул. Пирогова, 2, Новосибирск 630090

Аннотация: Доказывается вложимость структуры тьюринговых степеней в структуру степеней по экзистенциальной интерпретируемости. В доказательстве естественным образом возникает понятие слабо ограниченной тьюринговой сводимости ($\operatorname{wbT}$-сводимости). Доказывается, что эта сводимость расположена строго между ограниченной табличной и тьюринговой сводимостями, а также отличается от табличной сводимости.

Ключевые слова: экзистенциальная интерпретируемость структур, слабо ограниченная тьюрингова сводимость.

УДК: 510.5

MSC: 35R30

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

DOI: 10.17377/smzh.2017.58.210


 Англоязычная версия: Siberian Mathematical Journal, 2017, 58:2, 281–287

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


© МИАН, 2024