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

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

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

Включим все условия задачи, доступные для переработки данным алгоритмом А, в занумерованную положительными целыми числами последовательность А₀, А₁, А₂, . . . , А_n, . . .

Совершенно аналогично записи возможных решений также включим в занумерованную последовательность В₀, В₁, В₂, . . . , В_m, . . .

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

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

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

Функции вида y=(x₁, x₂, . . . , x_n) назовём числовыми функциями, если как аргументы, так и сами функции могут принимать лишь целочисленные значения на N={0, 1, 2, ... }. В дальнейшем фиксированные целые числа будем обозначать a*, x*, y*, и т.д. Числовая функция y=(x₁, x₂, . . . , x_n) называется алгоритмически вычислимой или просто вычислимой, если существует алгоритм, позволяющий определить значение функции при любых значениях переменных х₁, х₂, . . . , х_n.

Числовая функция f, ставящая в соответствие элементу из Nⁿ натуральное число из N, называется n-местной функцией. Функция f, для которой область определения D_f не совпадает с Nⁿ (D_f является подмножеством Nⁿ), называется частичной числовой функцией. В приведенных определениях Nⁿ=NN . . . N - декартово произведение на множестве N натуральных чисел.

Введем понятие численного алгоритма, являющегося эффективной процедурой, которая используется для получения значений числовой функции. Если такая процедура существует, будем говорить, что функция эффективно вычислима (или просто вычислима). В качестве примера можно рассмотреть алгоритм нахождения наибольшего общего делителя двух натуральных чисел. Такому алгоритму можно сопоставить функцию z=HOD(x,y), значение которой z является наибольшим общим делителем х и y. Существует алгоритм нахождения n-го простого числа по данному номеру n. Такому алгоритму можно сопоставить функцию y=f(n), значением которой является простое число, n-e по порядку. Приведенные примеры являются примерами эффективно вычислимых функций, поскольку для них существуют численные алгоритмы. Можно рассмотреть пример невычислимой функции, то есть функции, для которой не существует эффективной вычислительной процедуры. Введем функцию g(n) следующим образом:

1, если в десятичном разложении числа  найдется ровно n цифр 7,

g(n)= стоящих подряд;

 0 в противном случае.

Такая функция существует, но является ли она вычислимой? Известна механическая процедура получения цифр в десятичном разложении , однако, в случае, если n семерок подряд не существует, процедура вычислений становится бесконечной, следовательно, такая вычислительная процедура не будет эффективной (результат не будет получен после конечного числа шагов).

Данное выше определение числовой функции является интуитивным. Для того, чтобы уточнить это определение, построим класс вычислимых функций. Начнём построение с понятия элементарных функций. Элементарными будем называть арифметические функции, полученные на множестве натуральных чисел с помощью конечного числа сложений, вычитаний (результатом вычитания будет |x-y|), умножений и делений (деление в области натуральных чисел будем понимать как получение целой части частного [a/b] и остатка rest(a,b) при b  0).

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

Примерами элементарных функций могут быть простые функции вида (x)=x+1, (y)=12y, (a, b, c)=ab+c, (b)=b² и многие другие. Возникает вопрос, шире ли класс всех вычислимых функций класса элементарных функций? Оказывается, можно построить вычислимую функцию, не являющуюся элементарной. Это позволяет нам сделать вывод, что для построения всех вычислимых функций класс элементарных функций нуждается в расширении. Введем класс функций, в основу определения которых положен метод математической индукции.

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

Одним из простейших видов рекурсии является примитивная рекурсия. Для построения множества примитивно - рекурсивных функций введем множество простейших, первоначально известных функций, исходя из которых можно получить новые функции. Введем три типа простейших функций:

1. Функции любого числа независимых переменных, значения которых тождественно равны нулю при любых значениях аргументов: Oⁿ(x₁, x₂, . . . , x_n) = 0.

2. Функции выделения аргумента, которые мы будем обозначать Iⁿ_m, работающие по правилу: значением функции Iⁿ_m, зависящей от n аргументов, считать значение m - го аргумента (1 m  n). Например, для функции I³₂(x,y,z) значением функции будет значение аргумента y.

3. Функция "следование за", которая обозначается далее S(x)=x' , и означает переход к следующему натуральному числу: 0'=1, 1'=2, 2'=3, ... , x'=x+1.

Алгоритмы, соответствующие этим функциям, являются наиболее простыми.

Операции, с помощью которых можно исходя из простейших функций строить новые, относящиеся к классу рекурсивных, будем далее называть операторами. Оператор суперпозиции, или подстановки, это оператор, который по функции F от n аргументов x₁, x₂, ... , x_n и по заданным функциям f₁, f₂, . . . , f_n от одного и того же числа m аргументов строит новую функцию

g(x₁, x₂, . . . , x_m)=F(f₁(x₁, ... , x_m), f₂(x₁, ... , x_m), . . . , f_n(x₁, ... , x_m)).

Будем говорить, что функция g получается суперпозицией или подстановкой из функций F, f₁, f₂, ... ,f_n.

Оператор рекурсии является уточнением и расширением схемы определения функции по индукции. Пусть заданы какие-нибудь числовые частичные функции: n- местная функция g и (n+2)- местная h. Оператор рекурсии строит по этим функциям функцию f от (n+1) аргумента по следующим правилам: для всех натуральных значений x₁, x₂, . . . , x_n, y

f(x₁, x₂, x₃, ... , x_n, 0)= q( x₁,x₂, x₃, . . . , x_n)



f(x₁, x₂, x₃, ... , x_n, y+1)= h(x₁, x₂, . . . , x_n, y, f(x₁, x₂, x₃, ... , x_n, y)).

Обозначим символически применение оператора рекурсии к функциям g, h как

f=R(g, h).

Здесь R можно рассматривать как символ двуместной частичной операции, определенной на множестве всех частичных функций.

В случае n=0 скажем, что одноместная частичная функция f возникает в результате применения оператора рекурсии к одноместной функции, имеющей постоянное значение а, и двуместной частичной функции h, если

f(0)=a



f(x+1)=h(x, f(x))

Чтобы при заданных частичных функциях g, h найти значения функции f, полученной из них применением оператора рекурсии, последовательно находим:

f(x₁, x₂, . . . , x_n, 0)=g(x₁, x₂, . . . ,x_n),

f(x₁, x₂, . . . , x_n,1)=h(x₁, x₂, . . . , x_n, 0, g(x₁, x₂, . . . , x_n)),

. . .

f(x₁, x₂, . . . , x_n, m+1)=h(x₁, x₂, . . . , m, f(x₁, x₂, . . . , x_n))

и таким образом f определена однозначно. Из приведенных соотношений видно, что, если при некоторых x₁, x₂, . . . , x_n, t значение f(x₁, x₂, . . . , x_n, t) окажется неопределенным, то неопределенными будут и значения f(x₁, x₂,. . . , x_n, y) при всех yt.

Теперь введем одно из главных понятий теории рекурсивных функций. Пусть задана система  каких-то частичных функций. Частичная функция f называется примитивно-рекурсивной относительно , если f можно получить из функций системы  и простейших функций S, O, Iⁿ_m конечным числом операций подстановки и примитивной рекурсии.

Функция f называется просто примитивно-рекурсивной, если ее можно получить конечным числом операций подстановки и примитивной рекурсии, исходя лишь из простейших функций S, O, Iⁿ_m.

Операции подстановки и примитивной рекурсии, будучи применены к всюду определенным функциям, дают в результате снова всюду определенные функции. Поэтому, если задана система  всюду определенных функций, то примитивно-рекурсивные относительно  функции будут всюду определенными. В частности всюду определенными будут все примитивно-рекурсивные функции.

Наконец, из определения также непосредственно вытекает, что операции подстановки и примитивной рекурсии, примененные к частичным функциям, примитивно-рекурсивным относительно какой-нибудь системы , дают в результате снова функции, примитивно-рекурсивные относительно .

Приведем примеры построения некоторых примитивно-рекурсивных функций.

Пример 1.9.

Определим примитивно- рекурсивную функцию f(y,x) так:

f( 0, x)= x

f( y+1, x)= f( y, x) + 1

Согласно приведенной схеме получим

f( 1, x)=x+1, f( 2, x)=x+1+1=x+2, f(3, x)= x+2+1=x+3, . . . f( x+ y)=x+y,

то есть данная примитивно- рекурсивная функция представляет сложение двух натуральных чисел.

Пример 1.10. Для определения следующей рекурсивной функции воспользуемся тем, что функция сложения x+y уже определена как примитивно- рекурсивная функция. Рассмотрим следующую схему рекурсии:

f(0, x)=0

f(y+1, x)=f(y, x)+x.

Последовательно получим:

f(1, x)=f(0, x)+x=0+x=x

f(2, x)=f(1, x)+x=x+x=2x

f(3, x)=f(2, x)+x=2x+x=3x

. . .

и вообще f(y, x)=yx.

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

Пример 1.11. Определим функцию "предшественник х"; ее значениями являются: pd(0)=0, pd(1)=0, pd(2)=1, pd(3)=2 и т.д. Эта функция определяется условиями

0 при x=0

pd(x)= 

|x-1| при x>0.

Такая функция - примитивно- рекурсивна, так как она определяется по схеме:

pd(0)=0

pd(x+1)=x .

Функция предшествования в дальнейшем используется для определения функции "усеченная разность", которая позволяет выполнять вычитание в области натуральных чисел и определяется следующим образом:

0 при xy,

x - y = 

|x-y| при x>y.

Пример 1.12. Доказать, что деление в области натуральных чисел есть примитивно- рекурсивная функция. Целочисленное деление в области натуральных чисел понимаем как получение целой части частного [a/b] и остатка rest(a, b). Докажем, что [a/b] есть примитивно- рекурсивная функция.

Пусть даны два числа х и у. Чтобы получить [x/y] надо найти целое i, такое, что следующее за ним (i+1) при умножении на у дает произведение, большее х: (i+1)y>x.

Отсюда естественно перейти к неравенству (i+1)yx+1. Построим равенство:

(x+1)-(i+1)y=0

По определению усеченной разности оно будет больше нуля в случае, если (х+1)>(i+1)y, и равно нулю при (х+1)(i+1)y. Рассмотрим простой пример: при х=9, у=2 построим такие усеченные разности.

j=0	(x+1)-(j+1)y=10-2 >0
j=1	(x+1)-(j+1)y=10-4 >0
j=2	(x+1)-(j+1)y=10-6 >0
j=3	(x+1)-(j+1)y=10-8 >0
j=4	(x+1)-(j+1)y=10-10 =0

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

Построим произведения вида

k

 ((x+1)-(j+1)y),

j=0

где k принимает значения 0, 1, 2, ... . Если среди сомножителей будет хотя бы один ноль, все произведение обратится в ноль. Возьмем Sg от произведения.

(Функция Sg(x) принимает значение 1 при х0 и 0 при х=0).

k=0	0 Sg( ((x+1)-(j+1)y))=1 j=0
k=1	1 Sg( ((x+1)-(j+1)y))=1 j=0
k=2	2 Sg( ((x+1)-(j+1)y))=1 j=0

Выражения, получаемые при различных значениях k, будут равны 1 до тех пор, пока мы не дойдем до наименьшего k=i, при котором (x+1)-(i+1)y=0. Начиная с этого момента все значения выражений будут равны нулю:

k=i	i Sg( ((x+1)-(j+1)y))=0 j=0
k=i+1	i+1 Sg( ((x+1)-(j+1)y))=0 j=0
. . .	. . .
k=x	x Sg( ((x+1)-(j+1)y))=0 j=0

Единице будут равны точно i из таких выражений, поэтому получим i как сумму:

x k i= (Sg( ((x+1)-(j+1)y))) k=0 j=0

Это i будет наименьшим числом, обладающим свойством, что следующее за ним, будучи умноженным на у даст произведение, превосходящее х. Таким образом, i=[x/y], если у0. Поскольку функции, которые были использованы при построении выражения для i, являются примитивно- рекурсивными, деление будет примитивно- рекурсивной функцией. Самостоятельно докажите, что rest(x,y) - примитивно- рекурсивная функция, используя уже доказанный факт, что [x/y] есть примитивно- рекурсивная функция.

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

Мы показали, что каждая примитивно- рекурсивная функция вычислима. Верно ли обратное? Всякая ли вычислимая функция примитивно- рекурсивна? Было доказано, что существуют вычислимые функции, не являющиеся примитивно- рекурсивными, то есть класс вычислимых функций шире, чем класс примитивно- рекурсивных. Для того, чтобы расширить класс рекурсивных функций, введем новый оператор - оператор минимизации.

Рассмотрим какую-нибудь n- местную (n1) частичную числовую функцию f. Допустим, что существует метод вычисления значений функции f, причем значение функции f будет неопределенным тогда и только тогда, когда алгоритм вычисления значения функции работает бесконечно, не выдавая результата. Зафиксируем значения первых (n-1) аргументов функции f:

x*₁, x*₂, . . . , x*_n-1

и рассмотрим уравнение f(x₁, x₂, . . . , x_n-1, y)=x_n.

Чтобы найти решение (натуральное) этого уравнения, будем последовательно вычислять значения f(x₁, x₂, . . . , x_n-1, y) для у=0, 1, 2, . . .

Рассмотрим пример f(x₁, x₂)=x₁+x₂. При х₁=2, х₂=5 уравнение f(2, y)=5 имеет решение у=3. При х₁=1, х₂=0 уравнение f(1, y)=0 не имеет решений в области натуральных чисел. Таким образом, уравнение

f(x₁, x₂, . . . , x_n-1, y)=x_n

не всегда разрешимо. Теперь рассмотрим случай, когда в этом уравнении аргументы x₁, x₂, . . . , x_n-1 не фиксированы, а могут принимать произвольные значения. Для различных наборов аргументов, принимающих значения на N, может существовать множество решений уравнения. Выберем среди всех возможных решений наименьшее а, такое, что f(x₁, x₂, . . . , x_n-1, à)=х_n и обозначим его через

y(f(x₁, x₂, . . . , x_n-1, y)=x_n)

Если задана функция f, значение данного выражения зависит от выбора значений для параметров x₁, x₂, . . . , x_n-1, x_n , и поэтому

y(f(x₁, x₂, . . . , x_n-1, y)=x_n)

есть функция (частичная) от аргументов x₁, x₂, . . . , x_n-1, x_n. Обозначим эту функцию символически Mf и будем говорить, что эта функция получена путем применения оператора минимизации к функции f.

Процесс нахождения значений функции Mf будет продолжаться бесконечно в следующих случаях:

а) значение f(x₁, x₂, . . . , x_n-1, 0) не определено;

б) значения f(x₁, x₂, . . . , x_n-1, у) для у=0, 1, 2, . . . , а-1 определены, но отличны от x_n, а значение f(x₁, x₂, . . . , x_n-1, à) не определено;

в) значения f(x₁, x₂, . . . , x_n-1, у) определены и отличны от x_n.

В остальных случаях будет найдено наименьшее решение у=а уравнения

f(x₁, x₂, . . . , x_n-1, y)=x_n. Это решение будет значением выражения

y(f(x₁, x₂, . . . , x_n-1, y)=x_n).

Если заданная функция f одноместная, то функцию Mf часто обозначают через f^-1 и называют обращением функции f, или просто обратной функцией. Таким образом, f^-1(x)= y(f(x)=y). Например, для функций Sg и S обратными будут функции

х, если х=0,1

Sg^-1(x)= 

неопределенное значение, если х>1.

Соответственно

х-1, если х>0

S^-1(x)= 

неопределенное значение, если х=0.

Частичная функция f называется частично - рекурсивной относительно системы частичных функций , если f может быть получена из функций системы  и простейших функций O, S, Iⁿ_m конечным числом операций подстановки, примитивной рекурсии и минимизации.

Частичная функция f называется частично - рекурсивной, если f может быть получена из простейших функций O, S, Iⁿ_m конечным числом операций подстановки, примитивной рекурсии и минимизации.

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

1. Каждая частичная функция, примитивно- рекурсивная относительно системы функций , является и частично- рекурсивной относительно . В частности, все примитивно- рекурсивные функции частично- рекурсивны.

2. Класс частично- рекурсивных функций шире класса примитивно- рекурсивных функций, так как все примитивно- рекурсивные функции всюду определены, а среди частично- рекурсивных встречаются и функции, не всюду определенные, например, функции Sg^-1, S^-1, а также нигде не определенная функция f(x)=z(x+1+z=0).

3. Операции подстановки, примитивной рекурсии и минимизации, проведенные над функциями, частично- рекурсивными относительно системы , дают в результате функции, снова частично- рекурсивные относительно .

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

Характеристической функцией _А какого-нибудь множества натуральных чисел А называется одноместная функция, равная 0 в точках множества А и равная 1 в точках, не принадлежащих А. Частичной характеристической функцией множества А называется одноместная функция, равная 0 в точках множества А и не определенная в точках, не принадлежащих А.

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

Множество натуральных чисел А называется примитивно - рекурсивным, если его характеристическая функция примитивно- рекурсивна. Множество А называется частично - рекурсивным, если его частичная характеристическая функция частично- рекурсивна. Аналогично определяется понятие примитивно- рекурсивного и частично- рекурсивного множеств относительно системы функций .

Покажем, что каждое примитивно- рекурсивное множество является частично- рекурсивным. Действительно, пусть (х) - характеристическая функция какого-нибудь множества натуральных чисел А. Тогда функция ч(х), определяемая равенством ч(х)=0- (х) будет частичной характеристической функцией множества А. Поскольку операция вычитания частично- рекурсивна, из данной формулы следует, что функция ч(х) также частично- рекурсивна.

Имеется возможность строить многочисленные примеры частично- рекурсивных функций по следующему принципу. Пусть f(x) – какая-нибудь примитивно- рекурсивная функция и А – произвольное примитивно- рекурсивное множество натуральных чисел. Тогда частичная функция fч(x), определенная схемой

f(x), если xA ,

fч(x)= 

 не определена, если xA,

является частично- рекурсивной. В самом деле, по доказанному выше частичная характеристическая функция ч(х) множества А частично- рекурсивна. Из схемы определения fч(x) вытекает, что для всех значений х

fч(x)=f(x)+÷(x)

и значит функция fч(x) частично-рекурсивная.

Понятие частично- рекурсивной функции – одно из главных понятий теории алгоритмов. Его значение состоит в следующем. С одной стороны, каждая стандартно заданная частично- рекурсивная функция вычислима путем применения определенной процедуры “механического” характера, которая несомненно отвечает нашему интуитивному представлению об алгоритмах. С другой стороны, какие бы классы точно очерченных алгоритмов до сих пор фактически не строились, во всех случаях неизменно оказывалось, что числовые функции, вычислимые посредством алгоритмов этих классов, были частично- рекурсивными функциями. В настоящее время общепринятой является следующая естественнонаучная гипотеза, сформулированная Чёрчем.

Тезис Чёрча. Класс алгоритмически (или машинно) вычислимых частичных числовых функций совпадает с классом всех частично- рекурсивных функций.

Задачи.

1.	Используя результаты предыдущих примеров доказать, что возведение в степень есть примитивно- рекурсивная функция.
2.	Доказать, что х! есть примитивно- рекурсивная функция.
3.	Определим функцию усеченная разность для натуральных чисел следующим образом: x-y=0 при x<y и x-y=|x-y| при x>y. Доказать, что эта функция примитивно- рекурсивна.
4.	Доказать, что функция min(x, y) для натуральных чисел примитивно- рекурсивна.
5.	Доказать, что характеристическая функция Sg(x), определенная как Sg(x)=0 при x=0 и Sg(x)=1 при x>0 является примитивно- рекурсивной.
6.	Доказать, что характеристическая функция Sg(x), определенная как Sg(x)=1 при x=0 и Sg(x)=0 при x>0 является примитивно- рекурсивной.
7.	Доказать, что функция |x-y| является примитивно- рекурсивной. При доказательстве использовать усеченную разность.
8.	Доказать, что функция rest(x, y), равная остатку от деления х на y является примитивно- рекурсивной.
9.	Доказать, что функция [x:y], где [ ] означает взятие целой части от частного, является примитивно- рекурсивной.
10.	Доказать, что конечная сумма примитивно- рекурсивных функций есть примитивно- рекурсивная функция.
11.	Доказать, что конечное произведение примитивно- рекурсивных функций есть примитивно- рекурсивная функция.