Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 8 стр.

       При суперпозиции функции g(x) с этой же функцией получим функцию h(x) = g(g(x)) = x
+ 2.
    Используя подстановку и функции тождества, можно переставлять и отождествлять
аргументы в функции:

       f(x2, x1, x3, . . ., xn) = f(I22(x1, x2), I12(x1, x2), x3, . . ., xn);

       f(x1, x1, x3, . . ., xn) = f(I12(x1, x2), I12(x1, x2), x3, . . ., xn).

    Таким образом, если заданы функции тождества и операторы суперпозиции, то можно
считать заданными всевозможные операторы подстановки функций в функции, а также
переименования, перестановки и отождествления переменных.

          2.2.2. Оператор примитивной рекурсии
    Оператор примитивной рекурсии Rn позволяет определить (n+1) - местную функцию f
по двум заданным функциям, одна из которых является n- местной функцией g, а другая
(n+2) - местной функцией h.
    Функция f(x1, x2, ..., xn, y) получается оператором примитивной рекурсии из функций
g(x1, x2, ..., xn) и функции h(x1, x2, ..., xn, y, z), если:
    f(x1, x2, ..., xn, 0) = g(x1, x2, ..., xn);                         (2)
    f(x1, x2, ..., xn, y+1) = h(x1, x2, ..., xn, y, f(x1, x2, ..., xn, y)).
    Приведенная пара равенств (2) называется схемой примитивной рекурсии. Для
понимания операции примитивной рекурсии необходимо заметить, что всякую функцию от
меньшего числа аргументов можно рассматривать как функцию от большего числа
аргументов. Существенным в операторе примитивной рекурсии является то, что независимо
от числа переменных в f рекурсия ведется только по одной переменной у. Остальные n
переменных x1, x2, ..., xn на момент применения схемы (2) зафиксированы и играют роль
параметров.

          2.2.3. Оператор минимизации
    Отношение P(x1, x2, ..., xn) называется примитивно-рекурсивным, если примитивно-
рекурсивна его характеристическая функция:
                                                             1, если P( x 1 , x 2 ,..., x n ) - " истина" ,
                                  χ( x 1 , x 2 ,..., x n ) = 
                                                              0, если P( x 1 , x 2 ,..., x n ) - " ложь".
    Предикат называется примитивно-рекурсивным, если его характеристическая функция
примитивно-рекурсивна.
    Функция f(x1, x2, ..., xn) получается посредством оператора минимизации из предиката
P(x1, x2, ..., xn, z), если в любой точке значением функции f(x1, x2, ..., xn) является
минимальное значение z, обращающее предикат P(x1, x2, ..., xn, z) в значение «истина»:
                              f(x1, x2, ..., xn) = µz (P(x1, x2, ..., xn, z)),
где µz – оператор минимизации.

          2.2.4. Ограниченный оператор минимизации
    Функция f(x1, x2, ..., xn) получается ограниченным оператором минимизации из
предиката P(x1, x2, ..., xn, z) и функции U(x1, x2, ..., xn), если в любой точке значение этой
функции определено следующим образом:
    1) для любого z < U(x1, x2, ..., xn) такого, что P(x1, x2, ..., xn, z) = "истина", значение
функции f(x1, x2, ..., xn) = µz(P(x1, ..., xn, z)),
    2) не для любого z < U(x1, x2, ..., xn) такого, что P(x1, x2, ..., xn, z) = "истина", значение
функции f(x1, x2, ..., xn) = U(x1, x2, ..., xn).