Cтраница 2
Читатель, знакомый с общей теорией алгоритмов, может убедиться, что Ф - общерекурсивный [33] или даже примитивно рекурсивный оператор. Если же читателю известны классы функций, элементарных по Кальмару или по Сколему ( см., например, [31]), то оператор Ф может быть классифицирован как элементарный по Кальмару или по Сколему. [16]
Пусть 9 ( N) обозначает класс всех подмножеств N. Сформулируйте определение рекурсивного оператора Ф: 5 ( N) - 5 ( N), аналогичное определению рекурсивного оператора из Ft - F. Сформулируйте и докажите теоремы, соответствующие теоремам 1.4 и 1.5. ( Указание. А) должен эффективно зависеть от конечного объема положительной информации о принадлежности х множеству А. [17]
В этом параграфе рассматривается возможность выноса за пределы цикла операторов, аргументы которых являются функциями рекурсивно определяемых переменных. Внутри цикла они заменяются простыми рекурсивными операторами присваивания, аргументы которых не зависят от других переменных. [18]
Пусть 9 ( N) обозначает класс всех подмножеств N. Сформулируйте определение рекурсивного оператора Ф: 5 ( N) - 5 ( N), аналогичное определению рекурсивного оператора из Ft - F. Сформулируйте и докажите теоремы, соответствующие теоремам 1.4 и 1.5. ( Указание. А) должен эффективно зависеть от конечного объема положительной информации о принадлежности х множеству А. [19]
В этом и состоит суть приведенного ниже определения рекурсивного оператора. [20]