СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ

АННОТАЦИИ

Рассматриваются обобщенные вычисления на
машинах Тьюринга со специальным оракулом
$F$
и вводятся два аналога
$\alpha $-рекурсии
на
$F$-вычислимых
ординалах. Первый аналог определяется с помощью подходящей
формальной системы
$L(F)$,
второй~--- с помощью
$F$-вычислимых
отображений на кодах ординалов. Доказывается, что эти
подходы определяют один и тот же класс функций и соответствуют
$\alpha $-рекурсии,
релятивизованной к функции
$F$.
Введен аналог непроектируемого ординала и рассматривается его
связь с проблемой разрешимости ограниченного перечислимого
множества. Библиогр.~2.