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

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

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

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

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

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

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

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

3) Im (x 1 ,..., xn) = xm — функция выбора (или тождества).

m

Сразу отметим, что нуль–функция и функция выбора могут иметь разное число аргументов: 0 n (x 1 ,..., xn) и In (x 1 ,..., xn).

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

f (x 1 ,..., xm),

f 1(x 1 ,..., xn) ,..., fm (x 1 ,..., xn)

 

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

 

g (x 1 ,..., xn) = f (f 1(x 1 ,..., xn) ,... fm (x 1 ,..., xn)). (2. 1)

m

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

 

выражение

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

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

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

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

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

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

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

f (x 1 ,..., xn, 0) = g (x 1 ,..., xn),

f (x 1 ,..., xn, y + 1) = h (x 1 ,..., xn, y, f (x 1 ,..., xn, y)). (2. 2)

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

f (0) = a,

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

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

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

f (x 1 ,..., xn, 0) = g (x 1 ,..., xn),

f (x 1 ,..., xn, 1) = h (x 1 ,..., xn, 0, f (x 1 ,..., xn, 0)),

...

f (x 1 ,..., xn, y) = h (x 1 ,..., xn, y − 1, f (x 1 ,..., xn, 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),

f (x, y + 1) = f (x, y) + 1 = s (f (x, y)) = s (I 3(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).

 

Оператор минимизации

Вернемся к начальной цели, которую мы поставили — дать формальное опре- деление алгоритма как функции, принадлежащей некоторому конструктивно опре- деленному классу функций. Возможно, что определение примитивно–рекурсивных функций будет удовлетворять этой цели. Однако сначала надо практически убедить- ся в том, что частный случай алгоритмов — программы для ЭВМ — можно предста- вить примитивно–рекурсивными функциями. Заданные в определении примитивно– рекурсивных функций средства их конструирования позволяют использовать для на- писания алгоритмов простейшие функции, оператор суперпозиции и оператор прими- тивной рекурсии. Если рассматривать программную реализацию этих конструктив- ных элементов, то простейшие функции соответствуют некоторому базовому набору операций языка программирования, оператор суперпозиции — последовательному выполнению действий, а оператор примитивной рекурсии — рекурсивной процедуре или оператору цикла типа "for". Рассмотрим достаточность этих средств для кон- струирования любого алгоритма. Сначала введем в рассмотрение новый оператор, представляющий аналог оператора цикла типа "while". Поскольку такой цикл вы- полняется многократно при истинности некоторого условия, необходимо рассматри- вать предикаты, определяющие такие условия. Любой предикат принимает значения "ложь" и "истина с которыми нельзя производить арифметических действий. Для

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

{ 1, P (x 1 ,..., xn) = истина

χp (x 1 ,..., xn) =

0, P (x 1 ,..., xn) = ложь

Кстати, при реализации логических переменных в программах для ЭВМ также обычно используются именно числа 0 и 1 для машинного представления значений "ложь" и "истина".

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

Определение 2.3. Функция f (x 1 ,..., xn) получается оператором минимизации из предиката P (x 1 ,..., xn, z), если в любой точке (x 1, x 2 ,..., xn) значением функции f (x 1 ,..., xn) является минимальное значение z, обращающее предикат P (x 1 ,..., xn, z)

в истину. Оператор минимизации имеет обозначение

 

f (x 1 ,..., xn) = µz (P (x 1 ,..., xn, z)). (2. 3)

Для того, чтобы для любого предиката P (x 1 ,..., xn, z) найти минимальное зна- чение z, обращающее P (x 1 ,..., xn, z) в истину, нужно последовательно перебирать значения z = 0, 1, 2 ,.... Вычисление значения функции, заданной с помощью опера- тора минимизации, можно программно реализовать следующим образом:

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

{

int z=0;

while (P(x1,... xn,z)==0) z++; return z;

}

 

Пример. Пусть f (x, y) = µz (2∗ x + z = y +1). Предикат P (x, y, z) = (2∗ x + z = y +1) является примитивно–рекурсивным, т.к. его характеристическая функция является суперпозицией примитивно–рекурсивных функций и равна

sg (sg ((2 x + z)−˙(y + 1)) + sg ((y + 1)−˙(2 x + z))).

Вычислим значение f (1, 5):

 

z = 0,	P (1, 5, 0) =	Ложь,
z = 1, ... z = 4,	P (1, 5, 1) =   P (1, 5, 4) =	Ложь,   Истина.

Тогда f (1, 5) = 4. Рассмотрим вычисление f (5, 1). В этой точке функция не опре- делена, т.к. P (5, 1, z) = "Ложь"для любого значения z ∈ N.

Полученный пример показывает, что с помощью оператора минимизации из при- митивно–рекурсивных функций можно получить не всюду определенные функции, поэтому оператор минимизации выводит из класса примитивно–рекурсивных функ- ций. Попробуем сделать так, чтобы остаться внутри класса примитивно–рекурсивных функций, но оставить возможность использования циклов типа "while". Для этого достаточно при определении оператора минимизации ввести ограничение на измене- ние переменной z так, чтобы цикл всегда завершался после некоторого числа шагов. В общем случае такое ограничение должно являться функцией свободных перемен- ных x 1, x 2,..., xn.