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

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

Примитивно-рекурсивные функции

Примитивно-рекурсивные функции - это n-местные, тотальные функции

f: N” -> N,

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

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

succ: N -> N                                 (функция следующего числа),

zero(0):à N                (константная нуль-функция),

zero(1):Nà N              (одноместная нуль-функция),

Справедливы следующие равенства, однозначно характеризующие базовые функции:

succ(n) = n+1,

zero(0)(n) = 0,

zero(l)(n) = 0,

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

g: NӈN,

hi: N» -> N, 1£ i£ n,

примитивно-рекурсивны.

Тогда функция f: Nmà N,

специфицированная равенством    f=g.[h1,..., hn],

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

С помощью схемы примитивной рекурсии,

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

g: NkàN,

h: Nk+1àN заданные функции. Тогда схема

f(x1,...,xk,0)=g(x1,...,xk), (*)

f(x1, ..., xk, n+1) = h(x1, ..., хk, n, f(x1, ..., xk, n)),

индуктивно специфицирует однозначно функцию

f: Nk+1 ->N.

При этом (*) называется схемой примитивной рекурсии. Однозначность функции f доказывается просто полной индукцией. Поэтому также об индуктивном определении функции f.

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

f(x1, ..., xk, n) =h(x1, ..., xk, n-

h(x1,..., xk, n-2,

                           …

h(x1, ..., xk, 0, g(x1, ..., xk)) ... )).

Функцию f, специфицированную с помощью примитивной рекурсии над g и h,  обозначается также через pr(g, h). При этом рг можно трактовать как функционал следующего вида:

рг: ((Nk -> N) х (Nk+2àN))à (Nk+1® N).

Функционал pr примитивной рекурсии соответствует схеме определения. Пишется

f= pr(g, h)

в качестве сокращения для приведенной выше схемы (*).

Равенство вида

g(x1, ..., Хm) = E

для определения функции g с произвольным выражением Е, которое образовано из символов функций f1, ..., fn и идентификаторов x1, ..., xn,  может быть через применение композиции и проекции записано также в  форме равенства между функциями:

g=F,

причем выражение F построено из композиций функций f1, ..., fn и проекций. Такая нотация ведет к стилю «функционального программирования», при котором вместо применения функций используются только  композиции функций.

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

g:Nk->N,

h:Nk+2àN

есть Т-вычислимые функции, то pr(g, h) тоже Т-вычислима. Формально J

это можно показать путем построения из двух Т-машин для вычисления g g и h новой Т-машины, которая вычисляет pr(g, h).

Определение множества PR примитивно рекурсивных функции как наименьшее подмножество множества {f: N” -> N : n Î N} n-местных (тотальных) функций над натуральными числами N со следующими свойствами этих подмножеств:



(1) Все базисные функции входят в PR.

(2) Если g, h1 ,.., hn Î PR (пусть g есть n-местная, a h1, ..., hm - m-местные функции), то справедливо

g . [h1,..., hn] ÎPR.

(3) Если g (k-местная) и h ((k+2)-местная) принадлежат PR, то pr(g, h) также принадлежит PR.

Однако это - неявное определение. Поэтому существуют примеры примитивно-рекурсивных и непримитивно-рекурсивных функций. Функция

sign: N -> N,

где

sign(n)=0, если n = 0, sign(n)= 1, если  n > 0,

является примитивно-рекурсивной:

справедливо sign(0) = 0, sign(n+l) = 1.

Отсюда получается следующее применение схемы примитивной рекурсии для определения функции sign:

sign = pr(zero(0), succ . [zero(1) о [ п21

]]).

Функция case

case: N3 ->

N,

специфицируемая равенством

case(x,y,z)=   [ y,  если х =0; z, если x>0 ]

является примитивно-рекурсивной. Справедливо равенство

case(x, у, z) = у* (l-sign(x))+z * sign(x).

Это соответствует выражению :

case(x, у, z) = add(mult(y, sub(l, sign(x)))), mult(z, sign(x))).

Подставляя примитивно-рекурсивные функции add, mult, sub и sign, получается выражение, которое построено только средствами примитивно рекурсии.

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

(1) Все функции в PR тотальны.

(2) Все функции в PR Т-вычислимы.

(3) Существуют Т-вычислимые функции, которые не являются прими тивнo-рекурсивными.

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

Высказывание (3) получается тривиально из того обстоятельства, чтo существуют частичные функции, которые являются Т-вычислимым Однако это высказывание может быть также подтверждено на примере тотальной функции. Рассмотрим для этого функцию Аккермана

ack: N2->N,

специфицированную следующей (непримитивно-рекурсивной) схемой:

ack(n,m)=[m+1,если n=0; ack(n-1,1),если n>0,m=0; ack(n-1,ack(n,m-1)),

если n>0,m>0]

Функция ack с помощью этого различения случаев определяется индуктивно.


Тем самым она определяется однозначно, что просто показывается через индукцию. Конечно, функция Аккермана интуитивно вычислима. Ее Т-вычислимость можно показать путем задания машины Тьюринга, которая вычисляет эту функцию. Этого можно достигнуть путем  моделирования магазина на Т-машине

Функция ack не является примитивно-рекурсивной. Фнкция ack состоит и множества примитивно-рекурсивных функций.

Теорема. Для любого числа n Î N функция Вn: N -> N,

специфицированная через

Теорема. Функция ack не является примитивно-рекурсивной.

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

m-рекурсивные функции

Примитивно-рекурсивные функции, соответственно определению, всегда являются тотальными. Как показывает пример функции Аккермана, существуют также тотальные функции, которые интуитивно являются вычислимыми и также

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

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

Пример (частично вычислимая функция). Для одноместной функции, заданной примитивно-рекурсивным определением (выражением), вычисляется ее наименьшее нулевое место - наименьшее натуральное число, для которого функция имеет значение 0 (т. е. min {х Î N: f (х) = 0}). Известно, что существует универсальная функция F (i, х), представляющая множество  всех  одноместных  частично  рекурсивных  функций (выражений).


Функция g, реализующая для универсальной функции указанное выше вычисление min по схеме m (см. ниже):

g(i) = min{x Î N: F(i, х) = 0},

является, очевидно, частичной и вычислимой. Заметим, однако, что функция g , доопределяющая функции g следующим образом:

g=[ g(i), если нулевое место существует; 1 в противном случае],

не является вычислимой (см. десятую проблему Гильберта).

Таким образом, имеются вычислимые функции, которые должны быть частичными (например, F (i, х)); не каждая частично вычислимая функция допускает доопределение до всюду определенной вычислимой функции (например, g (i)). Наряду с этим имеются алгоритмы, которые вычисляют всюду определенные (тотальные) функции, но для которых нельзя доказать завершаемость.

Пример (недоказанная завершаемость). Пусть отображение ulam специфицировано через

Ulam(n)=[1,n<1;ulam(g(n)) в противном случае]

причем функция g специфицирована следующим образом:

g(n)=[n/2,n- четно;$*n+1  иначе]

Обратим внимание, что функция g примитивно-рекурсивна. Это можно показать следующим образом. Отображение

Even(n)=[1,n-четно; 0  иначе]

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

В зависимости от вопроса, завершается ли вычислительное предписание ulam для всех аргументов, справедливы следующие высказывания:

(1)                Если предписание ulam завершается всегда, то для всех n Î N справедливо

ulam(n) = 1.  При этом предположении функция ulam примитивно-рекурсивна.

(2) Если для определенных входных значений ulam не завершается, то ulam есть частичная функция и потому определенно непримитивно-рекурсивна, так как примитивно-рекурсивная функция всегда тотальна. Форма описания функции ulam не позволяет сделать заключение, что эта функция является примитивно-рекурсивной.

До сих пор не удалось показать завершаемость функции ulam.

Очевидно, что формализм примитивной рекурсии не достаточно мощен.


Поэтому нужно расширить его так, чтобы также могли быть описаны и частичные функции.

Пусть задана частичная функция

f: Nk+1 -> “N (k Î N).

Специфицируем частичную функцию

m(f): Nkà N

через

m(f)(x1, ..., xk) = min {у Î N : f(x1, ..., xk y) = 0},

если существует такое число у ÎN, что

f(x1, ..., xk, у) =0

и для всех z < у значение функции f (х1, ..., хk, z) определено. Если такого числа у не существует, то значение применения функции m(f) к аргументу (x1, ..., хn) не определено.

Здесь говорится о принципе минимизациию

Функционал

m: (Nл+1

-> N) -> (NkàN),

который в описанной выше форме каждую (k+1)-местную функцию отображает

на k-местную функцию, называется также m-оператором.

Функция m(f) очевидно вычислима, если функция f вычислима. Это можно обосновать следующим образом. Можно тривиальным образом вычислять последовательно значения f(x1, ..., xn, 0), f(x1, ..., xn, 1),... до тех пор, пока не получится значение 0 как результат. Тогда можно закончить вычисления с соответствующим значением у в качестве результата. Если не существует нулевого места или же один из исследуемых вызовов не завершается до того, как будет найдено нулевое место, то такой способ не завершается. В этом случае применение функции m (f) не определено. Функции, которые могут быть определены на основании примитивно-рекурсивных функций с дополнительным применением m-оператора, называются m-рекурсивными.

Пример (m-рекурсивные функции). Следующие функции являются m-рекурсивными:

(1) Частично определенное вычитание

а-Ь= [a-b,  если а>Ь; не определено иначе.]

Определяется

а - b = m(hо)(а, b), где

ho:N3

-> N

есть примитивно-рекурсивная функция, специфицированная равенством

ho(a, b, у) = sub(b+y, a)+sub(a, b+y).

Здесь sub обозначает тотальное вычитание на натуральных числах

Sub(а,b)=[a-b, если а>b; sub(a,b)= 0 иначе]

m (ho) на самом деле есть искомая функция.

1.                   Случай а >.



b. Для у = а-b получается:

ho(a, Ь, а-Ь) = sub(b+(a-b), a)+sub(a, b+(a-b)) = 0.

Для у < а—b (т. е. для b+у< а)

справедливо: ho(a, b, у) = sub(b+y, a)+sub(a, b+y) = sub(a, b+y) > 0.

Таким образом, в этом случае имеет место ). m(ho)(a, b) = а—b.

2.         Случай а < b. Для всех чисел у получается:

ho(a, b, у) = sub(b+y, a)+sub(a, b+y) =

sub(b+y, а) > 0.

Таким образом, в этом случае m(Ьо) (а, b) не определено.

(2)                Деление. Частично определенное деление

a./.b=[a/b,a mod b=0; 0, a=b=0; не определено иначе]

специфицируется через m-рекурсию

m(h1),

где

h1(a, b, z) = а - (b * z).

Это снова можно показать путем различения случаев.

1.         Случай a mod b = 0 или а =Ь= 0;

Если имеет место b > 0, то число у однозначно определено и для z < у определено

a-b*z.. Если b = 0, то у = 0 удовлетворяет уравнению.

2.         Случай a mod b не равно 0 или b = 0 , а> 0; если b > 0, то справедливо а •/•b не определено.

Не существует такого числа z, что a-b*z= 0, так что выражение а - b * z или не определено, или оно > 0. Если а > 0 и b = 0, то

а - b*y > 0

для всех у; тогда m (h1) (а,b) не определено.

(3) ulam. Функция ulam специфицируется через

ulam(n) = succ(zero(l)(m( h )(n))), причем пусть функция g специфицирована так же, как и при введениифункции ulam в начале данного раздела, а функции h и h специфицированы следующим образом:

h(n, 0) = п,

h(n, m+l) = g(h(n, m)),

h(n, m) = sub(h(n, m)-1) == pred(h(n, m)).

Снова можно доказать, что для всех n Î N значение ulam (n) совпадает

со значением succ (zero(1))(m(h )(n))). Имеет место: ulam (n) = 1 или ulam (n) не определено.

(1)  h(n, m) = gm(n),     где go(n) =n,

(2)  h(n, m) = 0à h(n, m) < 1à g”’(n) < 1.

Поэтому m( h )(n) определена точно тогда, когда справедливо

Э m:gm(n) < 1,

и дает наименьшее число m, для которого это свойство имеет место.

Определяется множество MR m-рекурсивных функций как наименьшее подмножество пространства функций



{f: N” -> N: n Î N}

m- местных частичных отображений, для которого имеет место:

1.      MR содержит примитивно-рекурсивные функции PR,

2.      MR содержит все функции, которые можно получить путем композиции функций из MR,

3.      MR вместе с f содержит также m(f).

Множество MR охватывает все в общем смысле рекурсивно определимые функции над натуральными числами. Мы говорим о MR также как о множестве частично рекурсивных функций.

Общие объявления рекурсивных функций

m-рекурсия является частным случаем общего объявления рекурсии. На ряду с

m-рекурсией можно использовать следующие способы определения рекурсивных функций.

(1) Общая структурная рекурсия. Функции с функциональностью

f : N” -> N описываются через систему уравнений вида

f(ti1,...,tin)=Ri,

где терм Ri содержит только рекурсивные вызовы функций, включая f, базисные функции (как succ, zero и pred) и встречающиеся в левой части

уравнения идентификаторы хi, причем для термов tij. пусть справедливо

tij= xi+l или tij = 0.

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

Пример (функция Аккермана через структурную рекурсию). Функция Аккермана однозначно определяется уравнениями:

ack(0,0) = 1,

ack(0, m+l) = ack(0, m)+l,

ack(n+l, 0) = ack(n, 1),

ack(n+l, m+l) = ack(n, ack(n+l, m)).

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

Определение рекурсивности может быть обобщено от функций над натуральными числами на любые перечислимые множества М путем введения отображений

rep: М -> N («функция представления»),

abs: N -> М («функция абстракции»),

которые «интуитивно» являются вычислимыми и для которых равенство

abs(rep(m)) = m

справедливо для всех m Î М. Тогда функцию f: МàМ

назовем вычислимой точно тогда, когда существует вычислимая функция

g:N->N, такая, что

f (m) = abs(g(rep(m))).

Можно также, аналогично m-рекурсии, для примитивных рекурсий  или структурной рекурсии над натуральными числами ввести понятие вычислимости прямо над общими вычислительными структурам. Особенно просто можно понятие вычислимости распространить на предикаты над натуральными числами благодаря тому, что мы, например, значения false и true представим соответственно в виде 0 и 1.


Содержание раздела

---

---