Примитивно–рекурсивные функции

Всякий алгоритм для любых исходных данных однозначно определяет некото- рый результат, если, конечно, этот результат существует для них. Поэтому каждо- му алгоритму соответствует функция, которая вычисляет этот результат. Поставим цель дать формальное определение произвольного алгоритма как функции, принад- лежащей некоторому специальным образом построенному классу функций. Для то- го, чтобы определение такого класса функций было строго формальным, необходимо выбрать способ его задания. Воспользуемся конструктивным методом определения и опишем некоторый класс функций с помощью рекурсивных определений. Основным свойством конструктивного подхода является то, что все множество исследуемых объектов (в данном случае функций ) строится из конечного числа исходных объек- тов — базиса — с помощью простых операций, эффективная выполнимость которых

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

Рассмотрим сначала набор простейших функций, для которых с очевидностью

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

В качестве простейших функций будем использовать следующие три функции:

1. 0(x₁, . . . , x_n) = 0 — нуль–функция,

2. s(x) = x + 1 — функция следования,

3. I_m(x₁, . . . , x_n) = x_m — функция выбора (или тождества).

m

Сразу отметим, что нуль–функция и функция выбора могут иметь разное число аргументов: 0ⁿ(x₁, . . . , x_n) и Iⁿ (x₁, . . . , x_n).

Рассмотрим операторы, позволяющие конструировать новые функции из уже имеющихся. Введем в рассмотрение два оператора – оператор суперпозиции и опе- ратор примитивной рекурсии. Оператор суперпозиции из функций

f (x₁, . . . , x_m),

f₁(x₁, . . . , x_n), . . . , f_m(x₁, . . . , x_n)

строит новую функцию

g(x₁, . . . , x_n) = f (f₁(x₁, . . . , x_n), . . . f_m(x₁, . . . , x_n)). (2.1)

m

Обозначим оператор суперпозиции через S(f, f₁, . . . , f_m) или, с явным указанием числа аргументов функций, Sⁿ (f, f₁, . . . , f_m). Благодаря наличию функций выбора, стандартное представление суперпозиции с точным определением числа аргументов у всех функций f₁, f₂,..., f_m не уменьшает возможностей самого оператора суперпо- зиции, т.к. любую подстановку функции в функцию можно выразить через оператор S и функцию I. Например, для трех функций

выражение

x h(x, y) = x + y, f (x) = 3x − 1, g(x, y, z) = _{y + z}

x h(f (y), g(x, y, z)) = 3y − 1 + _{y + z}

2

можно представить в виде стандартной суперпозиции h(f (I³(x, y, z)), g(x, y, z)).

Следует отметить, что при наличии нуль–функции и функции следования, а так- же оператора суперпозиции можно построить все множество натуральных чисел:

0 = 0(x), 1 = s(0(x)), 2 = s(s(0(x))), . . . .

Рассмотрим оператор примитивной рекурсии. Известно, что рекурсия — это спо- соб вычисления значения функции в текущей точке через значение этой же функции в некоторых предыдущих точках. В зависимости от того, какие предшествующие точки используются при вычислении значения в текущей точке, рассматривают раз- личные схемы рекурсии.

Определение 2.1. Функция f (x₁, ..., x_n, y) получается оператором примитивной рекурсии из функций g(x₁, . . . , x_n) и h(x₁, . . . , x_n, y, z), если

f (x₁, . . . , x_n, 0) = g(x₁, . . . , x_n),

f (x₁, . . . , x_n, y + 1) = h(x₁, . . . , x_n, y, f (x₁, . . . , x_n, y)). ^(2.2)

Обозначим оператор примитивной рекурсии как R(g, h). Схема (2.2) называется схемой примитивной рекурсии. Например, при задании примитивно–рекурсивного описания функции одной переменной, схема примитивной рекурсии имеет вид:

f (0) = a,

f (x + 1) = h(x, f (x)),

где a — константа, принадлежащая множеству N .

Для того, чтобы в некоторой точке (x₁, . . . , x_n, y) вычислить значение функции, заданной оператором примитивной рекурсии, можно выполнить следующую конеч- ную последовательность вычислений:

f (x₁, . . . , x_n, 0) = g(x₁, . . . , x_n),

f (x₁, . . . , x_n, 1) = h(x₁, . . . , x_n, 0, f (x₁, . . . , x_n, 0)),

. . .

f (x₁, . . . , x_n, y) = h(x₁, . . . , x_n, y − 1, f (x₁, . . . , x_n, y − 1)).

Существенной характеристикой оператора примитивной рекурсии является такое его важнейшее свойство, что независимо от числа аргуменов функции f рекурсия ве- дется только по одному аргументу, остальные аргументы зафиксированы на момент применения рекурсии. Очевидно, что реализовать программное вычисление функ- ции, заданной оператором примитивной рекурсии, можно рекурсивным способом. Программа вычисления функции на языке Паскаль имеет вид:

function f(x1,...xn,y: integer): integer; begin if y=0 then f:= g(x1,..., xn)

else f:= h(x1,..., xn,y-1,f(x1,...,xn,y-1))

end;

Или на языке Си:

int f(int x1,..., int xn,int y)

{if (y==0) return g(x1,..., xn);

return h(x1,..., xn,y-1,f(x1,...,xn,y-1));

}

Можно использовать итерационный метод вычисления этой же функции. Для этого в программе достаточно организовать цикл, который выполняется столько раз, какова глубина вызова рекурсивной функции.

function f(x1,...xn,y: integer): integer; var t,i: integer;

begin t:= g(x1,..., xn);

for i:=0 to y-1 do t:= h(x1,..., xn, i, t); f:=t;

end;

Или соответственно на языке Си:

int f(int x1,...,int xn,int y)

{int t;

t= g(x1,..., xn);

for ( int i=0; i<y; i++ ) t= h(x1,..., xn, i, t); return t;

}

Обратите внимание, что цикл выполняется для переменной i, значение которой равно значению связанного рекурсией аргумента в предшествующей точке. Эти зна- чения равны 0, 1, ..., y − 1.

Определение 2.2. Функция называется примитивно – рекурсивной, если она мо- жет быть получена из простейших функций с помощью конечного числа операторов суперпозиции и примитивной рекурсии.

Данное определение эквивалентно рекурсивному заданию множества функций. Действительно, простейшие функции являются примивно–рекурсивными по опре- делению. Если некоторые функции являются примитивно–рекурсивными, то в ре- зультате применения к ним одного из операторов суперпозиции или примитивной рекурсии получаем новые примитивно–рекурсивные функции. Конечное число опе- раторов суперпозиции или примитивной рекурсии, которые применяются при по- строении примитивно–рекурсивных функций, гарантируют завершение указанного рекурсивного процесса. Таким образом, можно сформулировать рекурсивный ана- лог определения 2.2.

Рекурсивный вариант определения 2.2. Функция называется примитивно–

рекурсивной, если

а) она является простейшей,

б) она получена из примитивно–рекурсивных функций с помощью оператора су- перпозиции;

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

Других примитивно–рекурсивных функций нет.

Теорема 2.1. Примитивно рекурсивные функции всюду определены.

Доказательство. В соответствии с рекурсивным вариантом определения прими- тивно–рекурсивной функции достаточно рассмотреть три шага доказательства. Оче- видно, что простейшие функции всюду определены. Из определенных всюду функ- ций с помощью оператора суперпозиции можно получить только всюду определенные функции. Из определенных всюду функций в соответствии с алгоритмом вычисле- ния функций, заданных оператором примитивной рекурсии, также получаем всюду определенные функции. Q

Для доказательства примитивной рекурсивности некоторой заданной функции можно воспользоваться определением примитивно–рекурсивных функций, следова- тельно, существуют три направления поиска такого доказательства:

• показать, что заданная функция является простейшей,

• или показать, что заданная функция построена из примитивно–рекурсивных функций с помощью оператора суперпозиции,

• или показать, что заданная функция построена из примитивно–рекурсивных функций с помощью оператора примитивной рекурсии.

Пример. Доказать примитивную рекурсивность функции

f (x, y) = x + y.

Рассмотрим способ рекурсивного определения этой функции:

f (x, 0) = x,

f (x, y + 1) = x + y + 1 = f (x, y) + 1.

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

выбора и функцией следования:

f (x, 0) = x = I(x),

3

f (x, y + 1) = f (x, y) + 1 = s(f (x, y)) = s(I³(x, y, f (x, y))).

Аналогично можно доказать примитивную рекурсивность функций xy, x!, sg(x),

sg(x), x−^˙ y и т.д. Здеcь символ

сти:

−^˙ используется для обозначения усеченной разно-

^{ 0, если x < y

x−^˙ y =

x − y, если x ≥ y

Функция знака sg(x) равна нулю при x = 0 и единице во всех остальных точках

x ∈ N :

sg(x) =

^{ 0, x = 0

1, x > 0

Другая знаковая функция sg(x) возвращает отрицание знака:

sg(x) =

^{ 1, x = 0

0, x > 0.

Как уже отмечалось, суперпозицию функции f (x, y) и функций произвольного ви- да, не содержащих f (x, y), всегда можно представить в стандартной форме (2.2), если воспользоваться функцией выбора. Поэтому, если для некоторой функции f (x, y) мы провели доказательство ее примитивной рекурсивности с помощью оператора при- митивной рекурсии и для выражения f (x, y + 1) получили не стандартную форму су- перпозиции функции f (x, y) и известных примитивно–рекурсивных функций, то мы знаем, что получить стандартную форму (2.2) мы всегда можем. Поэтому в дальней- шем мы не всегда будем доводить процесс доказательства до конечной суперпозиции в стандартном виде (2.2).