Конспект установочных лекций по комплексному курсу Информатика, Теория информации




Рекурсивные функции - часть 8


{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.




Содержание  Назад  Вперед