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

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

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

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

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

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

Доказательство. Включим все условия задачи, доступные для переработки данным алгоритмом А в пронумерованную неотрицательными целыми числами последовательность А0, А1, А2, ..., АN, ...

Аналогично, записи возможных решений также включим в пронумерованную последовательность В0, В1, В2, ..., ВM, ...

После проведения нумерации очевидно, что любой алгоритм, перерабатывающий запись условий АN в запись решений ВM, можно свести к вычислению значений некоторой числовой функции m=(n), так как после проведения нумерации можно иметь дело лишь с соответствующими номерами записей условий и решений, а не с самими записями. Теорема доказана.

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

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

Действительно, чтобы найти значение (n) при n=n* (* означает конкретное значение n), можно по n* восстановить запись условия задачи, а затем по имеющемуся алгоритму найти запись решения и по ней определить номер m=m*, т. е. (n*)=m*.

Наоборот, если есть алгоритм вычисления функции (n), то имеется и алгоритм решения исходной задачи, т. к. по записи условия задачи можно найти соответствующий ей номер n*, затем вычислить m*=(n*) и по m* определить запись решения.

Один из методов такой нумерации был предложен австрийским математиком Куртом Геделем (род. 1906 г.). Любое целое неотрицательное число n можно представить в форме n=, где P0=2, P1= 3, 5, ...,PM-1, т. е. PI - i-е простое число.

В силу теоремы до единственности разложения любого числа на простые множители следует, что каждому числу n однозначно соответствует набор А={a1, a2, ... aM}, и, наоборот, каждому набору А однозначно соответствует число n.

Например, если n = 60, имеем 60=223151, т. е. a1=2, a2=1, a3=1.

Если n = 98, тогда 98=21305072, т. е. a1=1, a2=0, a3=0, a4=2.

С помощью этого способа (геделизации) можно нумеровать любые упорядоченные последовательности, состоящие из m чисел.

Приведем несколько примеров.

Пример 1. Каждой паре чисел a1 и a2, для которых мы ищем НОД = q, можно поставить в соответствие геделевский номер этой пары n=. Тогда алгоритм Евклида сведется к вычислению функции q=(n).

Пример 2. Пусть требуется перенумеровать все слова в некотором алфавите А. Это легко сделать, поставив каждой букве алфавита в соответствие какое-либо число. тогда каждому слову в алфавите А Будет соответствовать последовательность чисел (номеров букв). Осталось только вычислить геделевский номер этой последовательности. Возьмем для определенности алфавит русских букв А={а, б,в, г,д, е,ж, з,и,...э, ю,я} и пронумеруем их числами 1, 2, 3, 4, 5, 6, 7, 8, ... Вычислим геделевские номера некоторых русских слов. Слову "бег" соответствует набор {2, 6, 4}, т. е. n = 223654 = 4729625 = 1822500; слову "баба" соответствует набор {2, 1, 2, 1}, т. е n = 22315271 = 43257 = 2100.

Самостоятельно рассмотреть вопрос о возможности нумерации букв алфавита последовательностью 0, 1, 2, ...

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

Введем несколько основных понятий. Пусть X, Y - два множества. Частичной функцией (или отображением) из X в Y будем называть пару D(f), f, состоящую из подмножества D(f) X (называемого областью определения f) и отображения f: D(f) Y.

Если D(f) пусто, то f нигде не определена. Будем считать, что существует единственная нигде не определенная частичная функция.

Пусть A - алгоритм, X - множество возможных исходных данных алгоритма A, а результаты применения A принадлежат множеству Y. Будем говорить, что алгоритм A вычисляет частичную функцию f из X в Y, определенную равенством f(x) (результат применения A к X).

Примечание. Знак называется "условное равенство" и име ет следующий смысл. Если A и В суть какие-то выражения, то А В есть высказывание, утверждающее, что А и В одновремен но определены или не определены и, если определены, то имеют совпадающие значения. Например, высказывание истинно, а высказывание ложно (здесь х и у -- действительные переменные).

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

F: N N N, f(x, у) = х + у

Алгоритм деления уголком вычисляет функцию f из N N в N N, определенную на тех (т, п), для которых n 0, и при n 0 f (m, п) = (частное от деления т на п, остаток от деления т на п ).

Через N будем обозначать множество натуральных чисел. Через (N)N (при n 1) будем обозначать n-кратное декартово произведение множества N на себя, т. е. множество упорядоченных n-ок x1, x2,..., xN, xI N.

Основным объектом дальнейших построений будут частичные функции из (N)M в (N)N для различных m и n.

Частичная функция называется вычислимой, если существует вычисляющий ее алгоритм. Например, функции х + у, х у вычислимы. Композиция вычислимых функций также вычислима (покажите это). Нигде не определенная функция вычислима.

Понятие алгоритма имеет смысл, лишь если исходные данные и результаты - "конструктивные объекты". Так, не имеет смы сла (во всяком случае, без дополнительных уточнений и соглаше ний) говорить об алгоритме, входом которого является произволь ное множество действительных чисел, и даже об алгоритме, входом которого является действительное число. Мы будем избегать таких ситуаций, рассматривая алгоритмы, работающие с конструктивны ми объектами, такими, как натуральные числа, слова в конечном алфавите и т. п. Таким образом, вопрос о вычислимости функции f: X Y осмыслен, лишь если X и Y являются подмножествами "ансамблей конструктивных объектов". Примеры ансамбля кон структивных объектов: множество N натуральных чисел, множе ство Б* слов конечного алфавита Б.

В общем понимании, ансамбль -- это собрание конструктивных объектов "одного и того же типа". Разумеется, сказанное не явля ется определением в математическом смысле этого слова. Понятие ансамбля конструктивных объектов мы рассматриваем как интуитивное, неопределяемое понятие (так же, как и понятие конструк тивного объекта, натурального числа, множества).

Ансамбли обладают свойством: если X и Y - ансамбли, то X Y - также ансамбль (наличие у ансамблей этого свойства мы принимаем как аксиому).

Замечание. Часто возникающее заблуждение состоит в том, что для доказательства вычислимости функции f нужно не просто доказать существование вычисляющего ее алгоритма, но и предъ явить его. Ничего подобного! Функция

Вычислима, так как она равна либо функции, тождественно рав ной 0, либо функции, тождественно равной 1, а обе они вычислимы.

Задача. Будет ли вычислима функция f: N N, определяе мая так: f(x) равно нулю, если в десятичном разложении числа есть по крайней мере п девяток подряд, и единице в противном случае?

Дадим более строгое определение вычислимой функции.

Частичная функция f из (N)M в (N)N называется вычислимой, если можно указать такой алгоритм ("программу"), который для входного набора x (N)M дает на выходе f(x), если x D(f) и нуль, если x D(f).

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

Частичная функция из (N)M в (N)N полувычислима, если можно указать такой алгоритм (программу), который для входного набора x (N)M дает на выходе f(x), если x D(f), или алгоритм работает неопределенно долго, если x D(f).

Очевидно, что вычислимые функции полувычислимы, а всюду определенные полувычислимые функции вычислимы.

Частичная функция f называется невычислимой, если она не является ни вычислимой, ни полувычислимой.

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

Можно показать, что существует такой многочлен с целыми коэффициентами P(t, x1,..., xN), что g(t) - невычислима. Однако, легко видеть, что g(t) - полувычислима.

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

Простейшие функции:

Suc:

Определение следующего за x числа;

Определение "размерности" области определения функции;

"проекция" области определения на одну из переменных.

Элементарные операции над простейшими функциями:

А) композиция (или подстановка) ставит в соответствие каждой паре функций f из (N)M в (N)N и g из (N)N в (N)P функцию h = g?f из (N)M в (N)P, которая определяется как

D(g?f) = f-1(D(g)) = {x(N)M xD(f), f(x)D(g)} (g?f)(x) = (g(f(x));

Б) соединение ставит в соответствие частичным функциям fI из (N)Ni , i = 1,2,...k функцию (f1,...,fK) из (N)M в (N)N1Ч...Ч(N)Nk , которая определяется как

D((f1,..., fK)) = D(f1)?...?D(fK),

(f1,..., fK) (x1,..., xM) = f1(x1,..., xM),..., fK(x1,..., xM); В) рекурсия ставит в соответствие паре функций f из (N)N в N и g из (N)N+2 в N функцию h из (N)N+2 в N, которая определяется рекурсией по последнему аргументу

H(x1,...,xN, 1) = f(x1,...,xN) (начальное условие),

H(x1,...,xN, k+1) = g(x1,...,xN, k, h(x1,...,xN , k)) при k 1 (рекурсив. шаг).

Область определения D(h) описывается также рекурсивно:

X1,..., xN, 1 D(h) x1,..., xN D(h);

X1,..., xN, k +1 D(h) x1,..., xN, k D(h);

X1,..., xN, k, h(x1,..., xN, k) D(g) при k 1;

Г) операция m, которая ставит в соответствие частичной функции f из (N)N+1 в N частичную функцию h из (N)N в N, которая определяется как

D(h) = {x1,..., xN, k xN+1 1,

F(x1,..., xN, xN+1) = 1 и x1,..., xN, k D(f) для всех k xN+1},

H(x1,..., xN) = min{ xN+1 f(x1,..., xN, xN+1) = 1}.

Операция m позволяет вводить в вычисления перебор объектов для отыскания нужного в бесконечном семействе.

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

А) последовательность частичных функций f1, ..., fN называют частично рекурсивным (соответственно примитивно рекурсивным) описанием функции fN = f, если f1 - одна из простейших функций; fI для всех i 2 либо является простейшей функцией, либо получается применением одной из элементарных операций к некоторым из функций f1, ..., fI-1 (соответственно одной из элементарных операций, кроме m); Б) функция f называется частично рекурсивной (соответственно примитивно рекурсивной), если она допускает частично рекурсивное (соответственно примитивно рекурсивное) описание.

Теперь можно привести тезис Черча в обычной форме:

А) функция f полувычислима, если и только если она частично рекурсивна; Б) функция f вычислима, если и только если рекурсивны f и характеристическая функцияD(f).

Характеристическая функция подмножества X в Y (X Y) есть такая функция, что

Тезис Черча может использоваться как определение алгоритмической неразрешимости.

Пусть имеется счетная последовательность "задач" P1, P2, ..., которые имеют ответ "да" или "нет". Такая последовательность носит название "массовой проблемы". Свяжем с ней функцию f из N в N:

D(f) = {i | PI имеет ответ "да"};

F(i) = 1, если i D(f).

Массовая проблема P называется алгоритмически разрешимой, если функции f и D(f) частично рекурсивны. В противном случае P называется алгоритмически неразрешимой.

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

Похожие статьи