Всякий алгоритм однозначно ставит в соответствие исходным данным (в случае если определен на них) определенный результат. Поэтому с каждым алгоритмом однозначно связана функция, которую он вычисляет. Исследование этих вопросов привело к созданию в 30-х годах прошлого века теории рекурсивных функций. В этой теории, как и вообще в теории алгоритмов принят конструктивный, финитный подход, основной чертой которого является то, что все множество исследуемых объектов (в данном случае функций) строится из конечного числа исходных объектов – базиса – с помощью простых операций, эффективная вычислимость которых достаточна очевидна. Операции над функциями будем называть операторами.
Будем рассматривать только числовые функции, т.е. функции, аргументы и значения которых принадлежат множеству натуральных чисел N (в теории рекурсивных функций полагают N=0, 1, 2, …). Иначе говоря, числовой n-местной функцией называется функция, определенная на некотором подмножестве с натуральными значениями. Если область определения совпадает с множеством , т.е. , то говорят, что функция f всюду определенная, в противном случае – частично определенная.
Например:
– всюду определенная двуместная функция.
– частично определенная функция (она определена при x ³ y).
Рекурсивным определением функции принято называть такое определение, при котором значения функции для данных аргументов определяются значениями функции для более простых аргументов (уже вычисленных) или значениями более простых функций.
Простейшим примером рекурсивного определения являются числа Фиббоначи, представляющие собой последовательность чисел , удовлетворяющих условиям
,
т.е. числа 1, 1, 2, 3, 5, 8, 13 … Каждое последующее число является суммой двух предыдущих чисел.
Определим теперь конкретный набор средств, с помощью которых будут строиться вычислимые функции.
Примитивно-рекурсивные функции
Очевидно, что к вычислимым функциям следует отнести все константы, т.е. 0 и все натуральные числа 1, 2, 3 …
Однако в прямом включении бесконечного множества констант в базис нет необходимости. Для этого достаточно нуль функции 0(x)=0 и функции следования S(x)=x+1, чтобы получить весь натуральный ряд. Кроме того, в базис следует включить семейство функций проектирования (или введения фиктивных переменных)
.
Следующие всюду определенные числовые функции назовем простейшими:
1) 0(x)=0 – нуль-функция.
2) S(x)=x+1– функция следования.
3) , где – проектирующая функция.
Все эти функции вычислимы в интуитивном смысле.
Определим теперь операторы. Они обладают тем свойством, что, применяя их к функциям, вычислимым в интуитивном смысле, получаем функции, также вычислимые в интуитивном смысле.
1 Оператор суперпозиции. Суперпозиция является мощным средством получения новых функций из уже имеющихся. Напомним, что суперпозицией называется любая подстановка функций в функции. Оператором суперпозиции называется подстановка в функцию от m переменных m функций от n одних и тех же переменных. Например, для функций
(5-1)
В этом случае говорят, что n-местная функция получена с помощью оператора суперпозиции из m-местной функции и n-местных функций , если
.
2 Оператор примитивной рекурсии. Оператор примитивной рекурсии определяет -местную функцию f через n-местную функцию g и -местную функцию h следующим образом:
(5-2)
Пара равенств (2-2) называется схемой примитивной рекурсии.
Тот факт, что функция f определена схемой (5-2) выражается равенством . В случае, когда n=0, т.е. определяемая функция f является одноместной, схема (5-2) принимает более простой вид:
; (5-3)
где C – константа.
Схемы (5-2) и (5-3) определяют f рекурсивно не только через другие функции g и h, но и через значения f в предшествующих точках: значение f в точке y+1 зависит от значения f в точке y. Для вычисления понадобится k+1 вычислений по схеме (5-2) для . Пример – вычисление n!.
Существенным в операторе примитивной рекурсии является то, что независимо от числа переменных в f рекурсия ведется только по одной переменной y, остальные n переменных на момент применения схем (5-2) и (5-3) зафиксированы и играют роль параметров.
Функция называется примитивно-рекурсивной, если она может быть получена из нуль-функции , функции следования и проектирующей функции с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.
Этому определению можно придать более формальный индуктивный вид.
1. Функции , и для всех натуральных n, m, где m £ n, являются примитивно рекурсивными.
2. Если g1(x1, x2, …, xn), …, gm(x1, x2, …, xn), h(x1, x2, …, xn) примитивно рекурсивные, то – примитивно-рекурсивные функции для любых натуральных n, m.
3. Если и – примитивно рекурсивные функции, то – примитивно-рекурсивная функция.
4. Других примитивно-рекурсивных функций нет.
Из такого индуктивного описания нетрудно извлечь процедуру, порождающую все примитивно-рекурсивные функции.
Пример 1. Покажем, что сложение, умножение, возведение в степень примитивно-рекурсивно:
1. Сложение примитивно-рекурсивно:
;
.
Таким образом, , где .
2. Умножение примитивно-рекурсивно:
.
3. Возведение в степень примитивно-рекурсивно:
;
.