Морозов А. С.
Об отношении Σ-сводимости между допустимыми множествами

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

Morozov A. S.
On the relation of Σ-reducibility between admissible sets

Reducibility on admissible sets is studied which is a stronger version of the usual Σ-presentability of models. One of its informal prototypes is the interpretability of one computational device in the other. We obtain criteria of reducibility for recursively listed and pure sets, introduce the notion of jump, and prove exact boundaries for the ordinals of jumps. We also show that this reducibility is lifted to HYP-superstructures. Several results are proven on the relations of this reducibility to some known reducibilities.

Полный текст статьи / Full texts:

• PDF file (527 KB)
• PostScript file (1 MB)