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

Сиб. матем. журн., 2004, том 45, номер 3, страницы 634–652 (Mi smj1096)

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

Об отношении $\Sigma$-сводимости между допустимыми множествами

А. С. Морозов

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Изучается сводимость на допустимых множествах, являющаяся усилением обычной $\Sigma$-представимости моделей, неформальным прообразом которой может служить интерпретируемость одних вычислительных устройств в других. Получены критерии сводимости для рекурсивно развернутых и чистых множеств, введено понятие скачка и получены неулучшаемые оценки для ординалов скачков, показана переносимость сводимости на $\mathbb{HYP}$-надстройки. Приведены некоторые результаты о соотношении этой сводимости с уже известными сводимостями.

Ключевые слова: определимость, вычислимость, сводимость, допустимое множество.

УДК: 510.56

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


 Англоязычная версия: Siberian Mathematical Journal, 2004, 45:3, 522–535

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


© МИАН, 2024