|
Сибирский математический журнал, 2004, том 45, номер 3, страницы 634–652
(Mi smj1096)
|
|
|
|
Эта публикация цитируется в 16 научных статьях (всего в 16 статьях)
Об отношении $\Sigma$-сводимости между допустимыми множествами
А. С. Морозов Институт математики им. С. Л. Соболева СО РАН
Аннотация:
Изучается сводимость на допустимых множествах, являющаяся усилением обычной $\Sigma$-представимости моделей, неформальным прообразом которой может служить интерпретируемость одних вычислительных устройств в других. Получены критерии сводимости для рекурсивно развернутых и чистых множеств, введено понятие скачка и получены неулучшаемые оценки для ординалов скачков, показана переносимость сводимости на $\mathbb{HYP}$-надстройки. Приведены некоторые результаты о соотношении этой сводимости с уже известными сводимостями.
Ключевые слова:
определимость, вычислимость, сводимость, допустимое множество.
Статья поступила: 24.06.2003
Образец цитирования:
А. С. Морозов, “Об отношении $\Sigma$-сводимости между допустимыми множествами”, Сиб. матем. журн., 45:3 (2004), 634–652; Siberian Math. J., 45:3 (2004), 522–535
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/smj1096 https://www.mathnet.ru/rus/smj/v45/i3/p634
|
Статистика просмотров: |
Страница аннотации: | 313 | PDF полного текста: | 125 | Список литературы: | 46 |
|