8_2 (Мацнев А.П. - Математическая логика и теория алгоритмов - 2004)

8.3 Рекурсивные функции

Как известно алгоритм дает процедуру отыскания значений вычислимой функции. Но как отличить вычислимую функцию от невычислимой? Как традиционным математическим языком списать общий вид вычислимых функций. Для этого поступим так:

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

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

2. Произведем (мысленно) все возможные операции из п. 2
   над базовыми функциями из п. 1, по-разному комбинируя их в
   качестве аргументов, расширим набор функций Р путем включения туда вновь полученных функций; над новым набором Р вновь произведем все возможные операции из набора О, получим новые функции, которые вновь включим в множество Р и т. д.

Поскольку не ограничиваем сверху количество исполнений п. 3, то, таким образом, будем получать все новые и новые функции. Иначе говоря, пп.1-3 описывают построение некоторого бесконечного множества функций. Однако каждая конкрет­ная функция f из этого множества является результатом вы­полнения конечного числа операций, взятых из набора О над базовыми функциями. Таким образом, процесс построения f:

1. начинается с исходных данных, выбираемых из базового
   набора;

1. выполняется пошагово (в дискретном времени);

1. на каждом шаге выполняется одна из элементарных опера­ций (из набора О);

1. результат каждого шага строго определен;

5) процесс заканчивается через конечное число шагов.
Этот перечень дает нам возможность говорить об алгоритме

a_f построения функции f. Заметим, что мы не вносим саму функцию f в перечень исходных данных, т. е. не говорим об «универса­льном» алгоритме построения функции. Напротив, для раз­личных функций f₁ и f₂ алгоритмы будут различны. Более того, свойство массовости алгоритмов не выполняется, исходные дан­ные всегда одни и те же — базовый набор функций. Это позволя­ет говорить о том, что текст алгоритма (последовательность при­менения операций из О и места подстановок в эти операции операндов из базового набора) задает единственную функцию, а не множество функций. Тогда легко преобразовать алгоритм a_f построения функции в алгоритм вычисления значений функ­ции f(x₁, х₂, ..., х_п) введением и использованием в тексте исходных данных x₁, х₂ ..., х_n.

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

Базовый набор функций. Р = { 0(х), S(x), Iⁿ_m (x₁, x₂, ..., х_п )}. Эти функции рассматривались и для них были постро­ены машины Тьюринга, вычисляющие их значения по значениям аргументов. Таким образом, этот набор удовлетворяет выдвину­тым выше требованиям.

Система операций. В систему операций О входят три операции: суперпозиции , примитивной рекурсии  и минимизации .

1. Операция суперпозиции , получая n+1 операнд функции f₀, f₁, …,f_n, производит результат f=  (f₀, f₁, …,f_n). Считая все функции зависящими от одного и того же набора аргументов (можно просто объединить наборы аргументов всех участвую­щих в операции функций в один набор и, если j-я функция ранее не зависела от i- го аргумента, то мы считаем этот аргумент несу­щественным для данной функции), можем задать формулу для вычисления значений вновь образованной функции f:

f(x₁, x₂, …, x_n) = f₀(f₁ (x₁, x₂, …, x_k), …, f_n (x₁, x₂, …, x_k)),

где k — количество переменных в объединенном наборе перемен­ных функций с индексами от 1 до п.

Первый операнд (функция f₀) операции суперпозиции играет отличающуюся от других операндов роль — он задает формиро­вание сложной функции. Поэтому аргументы функции f₀ не вхо­дят в перечень аргументов результата операции суперпозиции, но количество их должно быть равно п. Это требование не огра­ничивает применимость операции суперпозиции, так как при бо­льшем (> п) количестве аргументов функции f₀, мы всегда можем расширить перечень операндов операции σ, добавив необходи­мое количество тождественных функций; тогда часть аргументов f₀ перейдет в состав аргументов функции-результата.

Все рассматриваемые функции являются частичными, т. е. не всюду определенными; могут существовать такие комбинации значений аргументов, для которых значение функции не сущест­вует. Например, функция f(x) = х/2 определена только на подмно­жестве четных значений аргумента; функция f(x) = х - 3 не опреде­лена для значений аргумента, равных 0, 1, 2. В таких случаях и функция-результат f операции суперпозиции не существует для некоторых комбинаций значений аргументов. Точнее, f(а₁, а_2, ..., а_k) не существует, если не существует хотя бы одно из значений f₁(а₁, а_2, ..., а_k), f_n(а₁, а_2, ..., а_k) или, если эти значения суще­ствуют и равны b₁,…,b_n, то не существует значение f₀(b₁,..., b_n). Таким образом, функция f также является частичной. Подобные замечания можно сделать и в отношении следующих двух опера­ций.

2
. Операция примитивной рекурсии имеет два операнда, f = = (g, h). Первый операнд, функция g, зависит от п аргументов, п > 0, а второй операнд, функция h, имеет в общем случае два дополнительных аргумента, хотя в том и другом случае некото­рые аргументы могут быть несущественными. Функция-резуль­тат f определяется следующими уравнениями примитивной ре­курсии:

Здесь рекурсия производится по последнему аргументу функции f: ее значение при аргументе у+1 вычисляется через ее же значение при аргументе, равном у, которое, в свою очередь, вы­числяется через значение функции f при аргументе, равному y-1, и так далее до значения аргумента, равного 0, при котором про­цесс определения через себя (возвратный процесс, процесс рекур­сии) заканчивается.

Можно, наоборот, процесс вычисления значения f(x₁, х₂, ..., х_n, у) начинать всегда с 0, получая значение в соответствии с пер­вым уравнением (начальным условием), а затем в соответствии со вторым уравнением вычислять значения функции при аргу­ментах, равных 1, 2, 3, ... и т. д. до достижения значения у (итера­ционный процесс).

Приведем несколько примеров использования операций при­митивной рекурсии и суперпозиции для пополнения базового на­бора Р новыми функциями.

1
. Сложение неотрицательных целых чисел, Add(x, у)= х + у задается следующими уравнениями:

Здесь функция g(x)=I¹₁(х)=х —тождественная функция, а функция h = S зависит существенным образом только от последнего своего аргумента, а именно, от Add(x,y).

1. У
   множение Mult(x,y) = x*y задается уравнениями

к
оторые используют уже построенную функцию сложения чисел и известные соотношения x*0 = 0, х* (у + 1) = х + х*у.

3. Возведение в степень Роwеr(x, у) = x^y. Уравнения имеют вид

4
. Всюду определенное уменьшение на единицу, т. е. функция, которую можно задать следующими соотношениями (не рекур­сивно):

У
равнения с использованием примитивной рекурсии и супер­позиции задают эту функцию в виде

т. е. функция g =0, а функция h зависит только от предпоследнего аргумента (у).

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

Далеко не все функции, значения которых могут быть вычис­лены, относятся к классу примитивно-рекурсивных функций. В операции  рекурсия производится по одной переменной. Если построить схему с рекурсией по двум переменным (двойная ре­курсия, рекурсия 2-й ступени), то с ее помощью будут получаться функции, не принадлежащие в общем случае классу примитив­но-рекурсивных. В качестве примера можно привести известные функции Аккермана, определяемые соотношениями

B(0, у) = 2 + y,

В(х+ 1, 0) = sg(x),

В(х + 1, у + 1) = В(х, В(х + 1, у)),

А(х) = В(х, х).

Здесь sg(x) — функция, значение которой равно нулю при x = 0 и равно единице в противном случае. В определении функ­ции В(х, у) рекурсия введена по обеим переменным. Эти соотно­шения позволяют вычислить значения функции В и, следователь­но, функции А для любых значений переменных. В теории алгоритмов доказано, что функция Аккермана А(х) растет быст­рее, чем любая примитивно-рекурсивная функция. Точнее, для любой одноместной примитивно-рекурсивной функции f{x) най­дется такое п. что для любого х > п имеет место А(х) > f(x). Следо­вательно, А(х) не является примитивно-рекурсивной.

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

3. Операция минимизации  имеет один операнд, f=  (g). Зна­чения функции f на заданном наборе аргументов х₁, х₂, ..., х_n по­лучаются следующим образом. Сначала с помощью функции g формируется уравнение g(x₁, х₂, ..., х_n-1 , у) = х_n, а затем отыскива­ется его решение относительно переменной у. Если таких реше­ний несколько, то берется минимальное из них (отсюда и назва­ние операции); оно и считается значением функции / на дан­ном наборе аргументов, f(х₁, х₂, ..., х_n). Операцию минимизации обычно записывают с помощью оператора минимизации _у в виде f(х₁, х₂, ..., х_n) = _y(f(х₁, х₂, ..., х_n-1, y)) = х_n, Может случиться, что уравнение не имеет ни одного решения. В этом случае счита­ется, что функция f не определена на заданном наборе ар­гументов.