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




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


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

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

Примитивно-рекурсивные функции - это 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.




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