Как известно алгоритм дает процедуру отыскания значений вычислимой функции. Но как отличить вычислимую функцию от невычислимой? Как традиционным математическим языком списать общий вид вычислимых функций. Для этого поступим так:
1. Возьмем несколько простых базовых функций, для которых очевидна, что они могут быть вычислены, составим из них набор Р.
2. Введем операции над функциями. Операции получают функции (а не значения функций) в качестве операндов и дают в результате новые функции. Эти операции также должны быть очевидны с математической точки зрения — не должно возникать сомнений в том, что из вычислимых функций с помощью операций получаются вновь вычислимые функции. Обозначим набор этих операций О.
3. Произведем (мысленно) все возможные операции из п. 2
над базовыми функциями из п. 1, по-разному комбинируя их в
качестве аргументов, расширим набор функций Р путем включения туда вновь полученных функций; над новым набором Р вновь произведем все возможные операции из набора О, получим новые функции, которые вновь включим в множество Р и т. д.
Поскольку не ограничиваем сверху количество исполнений п. 3, то, таким образом, будем получать все новые и новые функции. Иначе говоря, пп.1-3 описывают построение некоторого бесконечного множества функций. Однако каждая конкретная функция f из этого множества является результатом выполнения конечного числа операций, взятых из набора О над базовыми функциями. Таким образом, процесс построения f:
1) начинается с исходных данных, выбираемых из базового
набора;
2) выполняется пошагово (в дискретном времени);
3) на каждом шаге выполняется одна из элементарных операций (из набора О);
4) результат каждого шага строго определен;
5) процесс заканчивается через конечное число шагов.
Этот перечень дает нам возможность говорить об алгоритме
af построения функции f. Заметим, что мы не вносим саму функцию f в перечень исходных данных, т. е. не говорим об «универсальном» алгоритме построения функции. Напротив, для различных функций f1 и f2алгоритмы будут различны. Более того, свойство массовости алгоритмов не выполняется, исходные данные всегда одни и те же — базовый набор функций. Это позволяет говорить о том, что текст алгоритма (последовательность применения операций из О и места подстановок в эти операции операндов из базового набора) задает единственную функцию, а не множество функций. Тогда легко преобразовать алгоритм af построения функции в алгоритм вычисления значений функции f(x1, х2, …, хп) введением и использованием в тексте исходных данных x1, х2 …, хn.
Введем сейчас конкретные базовый набор функций Р и систему операций О для формирования множества функций. В качестве области определения функций возьмем n-кратное декартово произведение множества неотрицательных целых чисел. Сами функции, как и их аргументы также принимают значения из множества неотрицательных целых чисел. Таким образом, мы обеспечиваем возможность, хотя бы потенциальную, вычислять значения функций с помощью машин Тьюринга.
Базовый набор функций. Р = {0(х), S(x), Inm (x1, x2, …, хп )}. Эти функции рассматривались и для них были построены машины Тьюринга, вычисляющие их значения по значениям аргументов. Таким образом, этот набор удовлетворяет выдвинутым выше требованиям.
Система операций. В систему операций О входят три операции: суперпозиции s, примитивной рекурсии r и минимизации m.
1. Операция суперпозиции s, получая n+1операнд функции f0, f1, …,fn, производит результат f= s (f0, f1, …,fn). Считая все функции зависящими от одного и того же набора аргументов (можно просто объединить наборы аргументов всех участвующих в операции функций в один набор и, если j-я функция ранее не зависела от i- го аргумента, то мы считаем этот аргумент несущественным для данной функции), можем задать формулу для вычисления значений вновь образованной функции f:
f(x1, x2, …, xn) = f0(f1 (x1, x2, …, xk), …, fn (x1, x2, …, xk)),
где k — количество переменных в объединенном наборе переменных функций с индексами от 1 до п.
Первый операнд (функция f0) операции суперпозиции играет отличающуюся от других операндов роль — он задает формирование сложной функции. Поэтому аргументы функции f0 не входят в перечень аргументов результата операции суперпозиции, но количество их должно быть равно п. Это требование не ограничивает применимость операции суперпозиции, так как при большем (> п) количестве аргументов функции f0, мы всегда можем расширить перечень операндов операции σ, добавив необходимое количество тождественных функций; тогда часть аргументов f0 перейдет в состав аргументов функции-результата.
Все рассматриваемые функции являются частичными, т. е. не всюду определенными; могут существовать такие комбинации значений аргументов, для которых значение функции не существует. Например, функция f(x) = х/2 определена только на подмножестве четных значений аргумента; функция f(x) = х — 3 не определена для значений аргумента, равных 0, 1, 2. В таких случаях и функция-результат f операции суперпозиции не существует для некоторых комбинаций значений аргументов. Точнее, f(а1, а2, …, аk)не существует, если не существует хотя бы одно из значений f1(а1, а2, …, аk), fn(а1, а2, …, аk) или, если эти значения существуют и равны b1,…,bn, то не существует значение f0(b1,…, bn). Таким образом, функция f также является частичной. Подобные замечания можно сделать и в отношении следующих двух операций.
2. Операция примитивной рекурсии имеет два операнда, f = = r(g, h). Первый операнд, функция g, зависит от п аргументов, п > 0, а второй операнд, функция h, имеет в общем случае два дополнительных аргумента, хотя в том и другом случае некоторые аргументы могут быть несущественными. Функция-результат f определяется следующими уравнениями примитивной рекурсии:
Здесь рекурсия производится по последнему аргументу функции f: ее значение при аргументе у+1 вычисляется через ее же значение при аргументе, равном у, которое, в свою очередь, вычисляется через значение функции f при аргументе, равному y-1, и так далее до значения аргумента, равного 0, при котором процесс определения через себя (возвратный процесс, процесс рекурсии) заканчивается.
Можно, наоборот, процесс вычисления значения f(x1, х2, …, хn, у) начинать всегда с 0, получая значение в соответствии с первым уравнением (начальным условием), а затем в соответствии со вторым уравнением вычислять значения функции при аргументах, равных 1, 2, 3, … и т. д. до достижения значения у (итерационный процесс).
Приведем несколько примеров использования операций примитивной рекурсии и суперпозиции для пополнения базового набора Р новыми функциями.
1. Сложение неотрицательных целых чисел, Add(x, у)= х + у задается следующими уравнениями:
Здесь функция g(x)=I11(х)=х —тождественная функция, а функция h = S зависит существенным образом только от последнего своего аргумента, а именно, от Add(x,y).
2.
Умножение Mult(x,y) = x*y задается уравнениями
которые используют уже построенную функцию сложения чисел и известные соотношения x*0 = 0, х* (у + 1) = х + х*у.
3. Возведение в степень Роwеr(x, у) = xy. Уравнения имеют вид
4. Всюду определенное уменьшение на единицу, т. е. функция, которую можно задать следующими соотношениями (не рекурсивно):
Уравнения с использованием примитивной рекурсии и суперпозиции задают эту функцию в виде
т. е. функция g =0, а функция h зависит только от предпоследнего аргумента (у).
Класс функций, получаемых из базовых применением конечного числа операций двух типов — суперпозиции и примитивной рекурсии, называется классом примитивно-рекурсивных функций Рпр. В этот класс, кроме приведенных выше, входят многие функции. Их общим свойством является то, что они всюду определены.
Далеко не все функции, значения которых могут быть вычислены, относятся к классу примитивно-рекурсивных функций. В операции r рекурсия производится по одной переменной. Если построить схему с рекурсией по двум переменным (двойная рекурсия, рекурсия 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. Операция минимизации m имеет один операнд, f= m (g). Значения функции f на заданном наборе аргументов х1, х2, …, хnполучаются следующим образом. Сначала с помощью функции g формируется уравнение g(x1, х2, …, хn-1, у) = хn,а затем отыскивается его решение относительно переменной у. Если таких решений несколько, то берется минимальное из них (отсюда и название операции); оно и считается значением функции / на данном наборе аргументов, f(х1, х2, …, хn). Операцию минимизации обычно записывают с помощью оператора минимизации mу в виде f(х1, х2, …, хn) = my(f(х1, х2, …, хn-1, y)) = хn,Может случиться, что уравнение не имеет ни одного решения. В этом случае считается, что функция f не определена на заданном наборе аргументов.
В качестве примера можно рассмотреть функцию Dec = m (S), где S(x) — функция из базового набора, S(x) = х + 1. Соответствующее уравнение имеет вид S(y) = х и оно имеет решение у = х — 1 при х > 0 и не имеет решения при х = 0. Следовательно, Dec(x) = х — 1 при х > 0 и Dec(0)не существует.
Оператор минимизации для функций одной переменной является средством отыскания обратной функции; более сложную, но также связанную с обращением, роль он играет для функций многих переменных.
Приведенный пример показывает, что оператор минимизации может превратить всюду определенную функцию в частичную, т. е. выводить за пределы множества примитивно-рекурсивных функций. Множество функций, получаемых применением кбазовому набору Р конечного числа операций типа суперпозиции, примитивной рекурсии и минимизации называется множеством частично-рекурсивных функций и обозначается Рчр.
Множество Ррвсюду определенных функций из Рчрназывается множеством рекурсивных (или общерекурсивных) функций. Очевидно, что выполняются следующие соотношения:
Pпр Ì Pр Ì Pчр Ì Pч Ì
где Рч — множество всех частичных функций.
В частности, приведенные выше функции Аккермана являются общерекурсивными.
Выше было введено множество вычислимых функций Рвыч, т. е. таких функций, для которых может быть построена машина Тьюринга, вычисляющая значение функции по значениям аргументов. Функции базового набора Р, взятые нами за основу построения множества частично-рекурсивных функций, являются вычислимыми — это было показано в первой главе путем конструирования соответствующих программ машин Тьюринга. В теории алгоритмов доказываются следующие утверждения.
1. Класс Ряычзамкнут относительно операции суперпозиции s.
Иными словами, если в качестве операндов операции суперпози
ции взять вычислимые функции, то результат обязательно будет
вычислимой функцией.
2. Класс Рвыч замкнут относительно операции примитивной
рекурсии r.
3. Класс Рвыч замкнут относительно операции минимизации m.
Следствием этих трех утверждений является вложение
Рчр Í Рвыч
4. Всякая функция, вычислимая на машине Тьюринга, частично-рекурсивна.
Более того, существует теорема Клини о нормальной форме: Любая вычислимая функция f(х1, х2, …, хn) представима в форме
f(х1, …, хn) = Ff (х1, х2, …, хn, my (Gf(х1, х2, …, хn,y)= 0)),
где Ff, Gf — примитивно-рекурсивные функции.
Из четвертого утверждения следует, что Рвыч Í Рчр. Таким образом, классы частично-рекурсивных функций и функций, вычислимых машинами Тьюринга, совпадают: Рчр = Рвыч.
Вспомним, что класс вычислимых по Тьюрингу функций в соответствии с тезисом Тьюринга является формализацией нечетко очерченного класса алгоритмически (в интуитивном смысле) вычислимых функций. Тогда можно вслед за А. Черчем сформулировать следующий тезис: «Класс алгоритмически (или машинно) вычислимых частичных функций совпадает с классом всех частично-рекурсивных функций».