Специальная математика. Соловьев А.Е. - 70 стр.

    f(0) = const
    f(y) = h(y - 1, f(y - 1))

Функции, которые могут быть построены из примитивных с помощью операторов
суперпозиции и примитивной рекурсии называются примитивно-рекурсивными.

Пример: функция суммирования.
f(x, 0) = g(x) = I(x) = x
f(x, 1) = h(x, 0, f(x, 0)) = h(x, 0, x) = h`(I3(3)((x, 0, x)) = S(x) = x + 1
f(x, 2) = h(x, 1, f(x,1)) = h(x, 1, x+1) = S(x + 1) = x + 2
...
f(x, y) = h(x, 1, f(x, y - 1)) = S(f (x, y - 1)) = x + y
то есть в традиционной записи определение сложения, как примитивно-рекурсивной
функции, будет:
x + y = x + (y - 1) + 1

Функция умножения.
fp(x, 0) = y(x) = z(0) = 0
fp(x, 1) = h(x, 0, fp(x, 0)) = h(x, 0, 0) = h`(I1,3(3)((x, 0, 0)) = f(x, 0) = x
fp(x,2) = h`(x, fp(x, 1)) = f(x, x) = 2x
fp(x,y) = f(x, fp(x, y - 1))
то есть в традиционной записи определение умножения, как примитивно-рекурсивной
функции, будет
x*y = x*(y - 1) + x
3. -оператор.
    y[g(x1, ... , xn, y) = 0]
 где y - выделенная переменная.
Работу -оператора можно описать следующим образом.
  Выделяется переменная (здесь – у). Затем фиксируется значение остальных переменных (x1,
... , xn). Значение y последовательно увеличивается, начиная с нуля. Значением -оператора
будет значение y, при котором функция впервые обратилась в ноль. Значение -оператора
считается неопределенным, если функция вообще не принимает значения ноль, либо она
принимает отрицательое значение до того как примет значение ноль.
Пример.
Пусть функция g(х, y) = х – у + 3. Зафиксируем х = 1
 y[g(1, y) = 0] = 4
так как 1 – 4 + 3 = 0.
Класс (множество, которое может быть получено из примитивных функций с помощью
операторов суперпозиции, примитивной. рекурсии и -оператора, называется. множеством
частично-рекурсивных функций.
   Множество частично-рекурсивных функций совпадает с множеством вычислимых функций
- алгоритмически разрешимых задач.

                                  6.7. -исчисление

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

                                         — 70 —