Математическая логика и теория алгоритмов. Стенюшкина В.А. - 57 стр.

       2 Формальная теория вычислимости

       2.1 Рекурсивные функции
      .
      Рекурсивные функции (РФ) – один из наиболее распространенных вариа-
нтов математического уточнения понятия вычислимой арифметической функ-
ции, то есть вычислимой функции, аргументы и значения которой – натураль-
ные числа /4/. РФ являются частичными функциями, то есть функциями, не
обязательно всюду определенными. В связи с этим используют термин частич-
но рекурсивные функции как синоним РФ. РФ, определенные всюду на N, на-
зываются общерекурсивными. (N – множество всех натуральных чисел).

                 2.1.1 Операции над числовыми функциями

       Здесь под числами понимаются натуральные числа или ноль. Обозначим
эту совокупность через N={0, 1, 2, ...}. Пустое множество обозначается ∅. Час-
тичные функции из N×…×N=N(k) в N называются k - местными числовыми фу-
нкциями. Операции над числовыми функциями называются операторами.
       Определение Пусть f1,...,fn - частичные функции переменных x1,...,xm,
определенные на множестве A со значениями в множестве B, f - частичная фу-
нкция n переменных, определенная на множестве B, со значениями в множест-
ве C. Тогда говорят, что частичная функция g m переменных, определенная на
множестве A со значениями в множестве C равенством g(x1,...,xm) =
f(f1(x1,...,xm),...,fn(x1,...,xm)), получается операцией суперпозиции из функций f,
f1, …, fn. Обозначение операции суперпозиции: Sn+1 (индекс вверху означает чи-
сло функций).
       Определение Числовые функции s1(x)=x+1, оn(x1,…,xn)=0, Inm(x1,…,xn)=xm
(1≤m≤n, n=1,2,…) называются простейшими. (Индекс 1 иногда будем опускать).
       Пример - I23(I12, I13, I22) = I13.
       Определение Пусть заданы числовые частичные функции: g - n -местная,
h - (n+2) - местная, f - (n+1) - местная, причем

      f(x1,…,xn,0)=g(x1,…,xn);                                               (2.1)
      f(x1,…,xn,y+1)=h(x1,…,xn,y, f(x1,…,xn,y))

      Тогда говорят, что функция f возникает из g и h примитивной рекурсией.
      Для n=0 (2.1) принимает вид:

      f(0)=a - константа;
      f(x+1)=h(x, f(x)).                                                     (2.2)

     Равенства (2.1) или (2.2) позволяют последовательно вычислять значения
функции в точках y=0, 1, 2,... по значениям функций g и h.
     Обозначение операции рекурсии:
     f = R(g, h) ,                                                     (2.3)