Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Рекурсивные функции - часть 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 с помощью этого различения случаев определяется индуктивно.
