Машина Тьюринга и рекурсивные функции. Кацаран Т.К - 27 стр.

          Операция суперпозиции (подстановка) заключается в подстановке
одних рекурсивных функций вместо аргументов в другие рекурсивные
функции.
          Пусть даны числовые функции f ( x1 ,..., xm ) , g1 ( x1 ,..., xn ) , g 2 ( x1 ,..., xn ) ,
…, g m ( x1 ,..., xn ) и пусть
                                  h( x1 ,..., xn ) � f ( g1 ( x1 ,..., xn ),..., g m ( x1 ,..., xn )) .
Тогда будем говорить, что функция h получена с помощью подстановки
из функций f ( x1 ,..., xm ) , g1 ( x1 ,..., xn ) , g 2 ( x1 ,..., xn ) , …, g m ( x1 ,..., xn ) .
         Например, функция o( x1 ,..., xn ) � 0 получается с помощью подстановки

из функций o(x) и I m( n ) ( x1 , x2 ,..., xn ) � xm : o( x1 ,..., xn ) � o( I m( n ) ( x1 , x2 ,..., xn )) . А

функция s m( n ) ( x1 , x2 ,..., xn ) � xm � 1 – из функций s (x) и I m( n ) ( x1 , x2 ,..., xn ) � xm :

sm( n ) ( x1 , x2 ,..., xn ) � s ( I m( n ) ( x1 , x2 ,..., xn )).
          Рассмотрим операцию примитивной рекурсии. Эта операция строит
функцию от n+1 аргументов, если имеются две числовые функции
g ( x1 ,..., x n ) и функция h( x1 ,..., x n , x n �1 , x n � 2 ) (функция от n+2 аргументов,
n � 1 ). Таким образом, если требуется построить функцию от некоторого
числа аргументов, необходимо иметь две функции: одна из них g зависит
от числа аргументов, которое на единицу меньше, чем число аргументов в
строящейся функции f , а вторая функция h зависит от числа аргументов
на единицу большего числа аргументов функции f .
          Операция примитивной рекурсии определяется следующим образом:
          �                  f ( x1 ,..., xn ,0) � g ( x1 ,..., xn )
          �
          �                                                                       .
          � f ( x1 ,..., xn , y � 1) � h( x1 ,..., xn , y, f ( x1 ,..., xn , y ))
          �
          В развернутом виде имеем, когда y = 0:
           f ( x1 ,..., xn ,0) � g ( x1 ,..., xn ) .
          Если y = 1, то f ( x1 ,..., xn ,1) � h( x1 ,..., xn ,0, f ( x1,..., xn ,0)).
          Если y = 2, то f ( x1 ,..., xn ,2) � h( x1 ,..., xn ,1, f ( x1 ,..., xn ,1)) и т. д.

                                                                 27