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




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


Примитивная рекурсия соответствует функциональному представлению статической ограниченной итерации или повторению (ср. с “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 со следующими свойствами этих подмножеств:




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