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

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

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

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

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

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

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

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

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

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

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

f (x1, . . . , xm),

f1(x1, . . . , xn), . . . , fm(x1, . . . , xn)

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

g(x1, . . . , xn) = f (f1(x1, . . . , xn), . . . fm(x1, . . . , xn)). (2.1)

m
Обозначим оператор суперпозиции через S(f, f1, . . . , fm) или, с явным указанием числа аргументов функций, Sn(f, f1, . . . , fm). Благодаря наличию функций выбора, стандартное представление суперпозиции с точным определением числа аргументов у всех функций f1, f2,..., fmне уменьшает возможностей самого оператора суперпо- зиции, т.к. любую подстановку функции в функцию можно выразить через оператор 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

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

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

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

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

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

f (x1, . . . , xn, 0) = g(x1, . . . , xn),

f (x1, . . . , xn, y + 1) = h(x1, . . . , xn, y, f (x1, . . . , xn, y)). (2.2)

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

f (0) = a,

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

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

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

f (x1, . . . , xn, 0) = g(x1, . . . , xn),

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

. . .

f (x1, . . . , xn, y) = h(x1, . . . , xn, y − 1, f (x1, . . . , 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(I3(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 (x1, . . . , xn) = истина

χp(x1, . . . , xn) =

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

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

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

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

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

f (x1, . . . , xn) = µz (P (x1, . . . , xn, z)). (2.3)

Для того, чтобы для любого предиката P (x1, . . . , xn, z) найти минимальное зна- чение z, обращающее P (x1, . . . , 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((2x + z)−˙(y + 1)) + sg((y + 1)−˙(2x + 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 так, чтобы цикл всегда завершался после некоторого числа шагов. В общем случае такое ограничение должно являться функцией свободных перемен- ных x1, x2,...,xn.


Наши рекомендации