Математическая логика и теория алгоритмов. Сергиевская И.М. - 41 стр.

     Простейшие                  примитивно-рекурсивные                   функции     задаются     следующим
образом.

• Функция следования задается формулой: s ( x) = x + 1 (или s1 ( x) = x + 1).

• Функция аннулирования задается формулой: 0( x) = 0 .

• Функция                    тождества                   определяется      следующим        образом:
     n
  I i ( x1 , x2 ,..., xi ,..., xn ) = xi , 1 ≤ i ≤ n , то есть эта функция произвольному n -мерному
  вектору сопоставляет его i -ю координату.

     Из простейших примитивно-рекурсивных функций         можно получить
примитивно-рекурсивные функции с помощью следующих двух операторов.

• Оператор суперпозиции. Пусть f n ( x1 , x2 ,..., xn ) , g1m (t1 , t 2 ,..., t m ) , g 2m (t1 , t 2 ,..., t m ) ,
   …, g nm (t1 , t 2 ,..., t m ) – примитивно-рекурсивные функции. Тогда функция
    Fnm ( g1m , g 2m ,..., g nm ) =
   = f n ( g1m (t1 , t 2 ,..., t m ), g 2m (t1 , t 2 ,..., t m ),..., g nm (t1 , t 2 ,..., t m ))
   получена с помощью оператора суперпозиции.
           Оператор суперпозиции – это оператор построения сложной функции. Если
   мы умеем вычислять функции g1m , g 2m , …, g nm и f n , то значения функции Fnm
   могут быть получены последовательным вычислением значений функций                                         g1m ,
    g 2m , …, g nm на некотором наборе значений a1 , a2 ,..., am переменных t1 , t 2 ,..., t m , и
   вычислением значения функции                                 f n на наборе значений g1m (a1 , a2 ,..., am ) ,
    g 2m (a1 , a2 ,..., am ) , …, g nm (a1 , a2 ,..., am ).

         Пример. Функция f ( x) = 1 получается суперпозицией функций 0(x) и s(x):
 f ( x) = s (0( x)) . Аналогичным образом можно получить функции вида f ( x) = n для
всех значений n.

• Оператор примитивной рекурсии из известных примитивно-рекурсивных
  функций ϕ n ( x1 , x2 ,..., xn ) и ψ n+ 2 ( x1 , x2 ,..., xn , y, z ) позволяет строить новую
    функцию f n +1 ( x1 , x2 ,..., xn , y ) . Так,
    f n+1 ( x1 , x2 ,..., xn ,0) = ϕ n ( x1 , x2 ,..., xn ) ,
    f n+1 ( x1 , x2 ,..., xn , y + 1) =
    = ψ n+ 2 ( x1 , x2 ,..., xn , y, f n+1 ( x1, x2 ,..., xn , y )) .




                                                                  46