8.2. Частично рекурсивные функции
Определим формальную систему, в которой определяются вычислимые числовые функции, отображающие числа из N или наборы чисел из N во множество N.
8.2.1. Простейшие функции
Следующие функции называются простейшими:
тождественный ноль О(x) = 0;
функция следования S(x) = x + 1;
функции проекции
(x1,
... , xn),
где 1
m
n.
Все эти функции являются вычислимыми, поскольку могут вычисляться с помощью очевидных алгоритмов.
8.2.2. Элементарные функции
Пусть заданы функции:
f(x1, . . . , xk), gi(xi1, . . . , xim i), i = 1, . . . , k.
Функция h(xj1, . . . , xjr) получается из заданных функций с помощью операции суперпозиции, если её можно представить в виде выражения:
f(g1(x1,1, . . . , x1,m1), . . . , gk(xk,1, . . . , xk,mk)).
Здесь переменными функции h являются все различные переменные функций gi(xi,1, . . . , xi,mi), i = 1, . . . , k.
Если все функции f(x1, . . . , xn), gi(xi1, . . . , ximi), i = 1, . . . , k, являются вычислимыми, то вычислима и суперпозиция таких функций функция h.
ОПРЕДЕЛЕНИЕ
Функции, получаемые из простейших функций с помощью конечного числа применений операции суперпозиции, называются элементарными функциями.
Всякая элементарная функция является вычислимой.
Пример. Функция f(x) = x + 2 является элементарной, так как f(x) = S(S(x)).
Элементарными являются, в частности, все функции константы.
Например, функция f(x) = k , где k некоторое число из N, может быть выражена следующей суперпозицией:
S(...S(O(x)...), в которой функция следования S применяется k раз.
Упражнение. Показать, что если f(x1, . . . , xn) это элементарная функция, то она растет не быстрее, чем некоторая линейная функция.
Существуют вычислимые числовые функции, которые не являются элементарными.
Например, функция f(x) = x2 не является элементарной.
8.2.3. Примитивно-рекурсивные функции
Пусть заданы функции:
g(x1, ... , xn) и h(x1, . . . , xn, xn + 1, xn + 2).
Функция f(x1, ... , xn+1) получается из функций g и h с помощью операции примитивной рекурсии, если справедливы соотношения:
f(x1, . . . , xn, 0) = g(x1, . . . , xn); (1)
f(x1, . . . , xn, y+1) = h(x1, . . . , xn, y, f(x1, . . . , xn, y)). (2)
Соотношения (1) и (2) называются схемой примитивной рекурсии. Соотношение (1) задает граничное условие, а соотношение (2) рекурсивно выражает значения функции f через другое значение этой функции.
Переменные x1, . . . , xn в схеме примитивной рекурсии представляют собой параметры. При этом допускается отсутствие параметров. В последнем случае функция g не имеет существенных переменных и является константой. Переменные xn+1 и xn+2 называются соответственно переменной рекурсии и переменной для рекурсивного вызова.
Предположим, что функции g и h являются вычислимыми. В этом случае функция f также является вычислимой.
Действительно, для нахождения значения f(x1, . . . , xn+1) можно воспользоваться следующей процедурой:
1. Вычислить значение f(x1, . . . , xn, 0), используя алгоритм вычисления функции g и соотношение (1) схемы примитивной рекурсии.
2. Используя соотношение (2) и алгоритм вычисления функции h, можно последовательно вычислить значения
f(x1, . . . , xn, 1), . . . , f(x1, . . . , xn, xn+1).