Примитивно–рекурсивные функции
Всякий алгоритм для любых исходных данных однозначно определяет некото- рый результат, если, конечно, этот результат существует для них. Поэтому каждо- му алгоритму соответствует функция, которая вычисляет этот результат. Поставим цель дать формальное определение произвольного алгоритма как функции, принад- лежащей некоторому специальным образом построенному классу функций. Для то- го, чтобы определение такого класса функций было строго формальным, необходимо выбрать способ его задания. Воспользуемся конструктивным методом определения и опишем некоторый класс функций с помощью рекурсивных определений. Основным свойством конструктивного подхода является то, что все множество исследуемых объектов (в данном случае функций ) строится из конечного числа исходных объек- тов — базиса — с помощью простых операций, эффективная выполнимость которых
достаточно очевидна. Операции над функциями в дальнейшем будем называть опе- раторами.
Рассмотрим сначала набор простейших функций, для которых с очевидностью
существуют алгоритмы их вычисления, а затем введем специальные операторы над числовыми функциями, с помощью которых можно будет из имеющихся функций получать новые функции.
В качестве простейших функций будем использовать следующие три функции:
1) 0(x1, . . . , xn) = 0 — нуль–функция,
2) s(x) = x + 1 — функция следования,
3) Im(x1, . . . , xn) = xm— функция выбора (или тождества).
| m |
Рассмотрим операторы, позволяющие конструировать новые функции из уже имеющихся. Введем в рассмотрение два оператора – оператор суперпозиции и опе- ратор примитивной рекурсии. Оператор суперпозиции из функций
f (x1, . . . , xm),
f1(x1, . . . , xn), . . . , fm(x1, . . . , xn)
строит новую функцию
g(x1, . . . , xn) = f (f1(x1, . . . , xn), . . . fm(x1, . . . , xn)). (2.1)
| m |
выражение
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
Следует отметить, что при наличии нуль–функции и функции следования, а так- же оператора суперпозиции можно построить все множество натуральных чисел:
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),
Аналогично можно доказать примитивную рекурсивность функций 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.