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



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


(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 с помощью этого различения случаев определяется индуктивно.


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