Введение в схемы, автоматы и алгоритмы


Примеры


Приведем некоторые примеры частично рекурсивных функций.

Пример 8.1. Постоянные функции.

Пусть fn(x1,…,xn)=k для всех наборов аргументов (x1,…,xn) и числа k

N. Тогда

f^n\ =\underbrace{ [s^1;[s^1;\ldots[s^1;}_{k \textit{ раз}}[o^1;I^n_1]]]\ldots]].

Пример 8.2. Сложение:+2(x,y)=x+y.

Функция сложения определяется следующей примитивной рекурсией.

\left \{ \aligned x&+0 =x = I^1_1(x) \\ x&+(y+1)=(x+y)+1=[s^1;(x+y)]=[s^1;\ I^3_3(x,y,x+y)] \endaligned \right .

Следовательно, +2 =R(I11,[s1;I33]).

Пример 8.3. Умножение: ?2(x,y)=x ? y.

Используя сложение, умножение можно задать следующей примитивной рекурсией:

\left \{ \aligned x&\times 0 =0 = o^1(x) \\ x&\times(y+1)=(x\times y)+x=I^3_3(x,y,x\times y)+I^3_1(x,y,x\times y) \endaligned \right .

Следовательно, ?2 =R(o1,[+;I33,I13]).

Пример 8.4. Минус 1:

\dot{-} 1(0)=0,\ \dot{-} 1(x+1)=x
.

Нетрудно проверить, что

\dot{-} 1 =R(0,I^2_1)
.

Пример 8.5. Вычитание :

\dot{ -} y = x-y
, если x
y и
x\dot{-} y=0,
если x < y.

Вычитание определяется следующей примитивно рекурсивной схемой:

\left \{ \aligned x&\dot{-} 0 =x = I^1_1(x) \\ x&\dot{-} (y+1)=(x\dot{-} y)\dot{-}1= [\dot{-}1^1;I^3_3(x,y,x\dot{-} y)] \endaligned \right .

Следовательно,

\dot{-}^2 =R(I^1_1,[\dot{-}1^1;I^3_3])
.

Пример 8.6. Предикаты равенства и неравенства нулю:

 sg(x)=\left \{ \aligned 0,\qquad \textit{если}\ x=0\\ 1,\qquad \textit{если}\ x\neq 0 \endaligned \right . \qquad \overline{sg}(x)= \left \{ \aligned 1,\qquad \textit{ если }\ x=0\\ 0,\qquad \textit{если}\ x\neq 0 \endaligned \right .

Примитивная рекурсивность этих функций следует из равенств

sg=R(0,[s^1;[o^1;I^2_1]])\
и
 \overline{sg}(x)=1 \dot{-} sg(x).

Пример 8.7. Модуль разности:

|x - y|=(x \dot{-}y)+(y \dot{-}x)
.

Пример 8.8.rm(x,y)= остаток от деления y на x (при x=0 положим rm(0,y)=y).

Заметим, что

rm(x, y+1)= \left\{ \begin{array}{ll} 0, & \mbox{ если } rm(x,y)+1=x \\ rm(x,y)+1, & \mbox{ если }rm(x,y)+1\ne x \end{array} \right.

Тогда функцию rm(x,y) можно задать примитивно рекурсивной схемой

\left \{ \aligned rm&(x,0)= 0, \\ rm&(x,y+1)=(rm(x,y)+1)sg(|x -( rm(x,y)+1)|) \endaligned \right .

Правую часть второго равенства легко представить как функцию g(x,y,rm(x,y)), полученную с помощью суперпозиции уже построенных примитивно рекурсивных функций.

Пример 8.9. Нигде не определенная функция ?(x).

Эта функция может быть задана, например, соотношением ?(x)= mu y[ s1(y)+x=0 ].

Отметим, что все функции в примерах 8.1 - 8.8 являются примитивно рекурсивными.




Начало  Назад  Вперед



Книжный магазин