Cтраница 4
Другая операция, участвующая в порождении новых примитивно рекурсивных функций, есть операция примитивной рекурсии. [46]
С другой стороны, следует отметить, что схема указанного вида, как и примитивная рекурсия, носит характер некоторого определения. [47]
Каждая частично рекурсивная функция получается из простейших арифметических функций с помощью операций суперпозиции, примитивной рекурсии и минимизации. [48]
Каждая частично рекурсивная функция конструируется из примитивно рекурсивных функций посредством применения операторов суперпозиции, примитивной рекурсии и наименьшего числа. Представляет интерес наименьшее число операторов, требующееся для образования частично рекурсивной функции из примитивно рекурсивных. A priori это число может быть сколь угодно велико. [49]
Другой возможный путь продолжения классификации Ш аналогичен методу Акста определения / ( с заменой примитивной рекурсии на двойную. Получающиеся при этом классы совпадают с классами Сп ( м), а эти последние замкнуты относительно ограниченной двойной рекурсии. Строгое доказательство этих фактов связано с весьма громоздкой техникой. Продолжение классификации связано с 6-кратными рекурсиями. [50]