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

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


Приведем некоторые примеры частично рекурсивных функций.
Пример 8.1. Постоянные функции.
Пусть fn(x1,…,xn)=k для всех наборов аргументов (x1,…,xn) и числа k
N. Тогда

Пример 8.2. Сложение:+2(x,y)=x+y.
Функция сложения определяется следующей примитивной рекурсией.

Следовательно, +2 =R(I11,[s1;I33]).
Пример 8.3. Умножение: ?2(x,y)=x ? y.
Используя сложение, умножение можно задать следующей примитивной рекурсией:

Следовательно, ?2 =R(o1,[+;I33,I13]).
Пример 8.4. Минус 1:
.
Нетрудно проверить, что
.
Пример 8.5. Вычитание :
, если x
y и
если x < y.
Вычитание определяется следующей примитивно рекурсивной схемой:

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

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

Пример 8.7. Модуль разности:
.
Пример 8.8.rm(x,y)= остаток от деления y на x (при x=0 положим rm(0,y)=y).
Заметим, что

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

Правую часть второго равенства легко представить как функцию g(x,y,rm(x,y)), полученную с помощью суперпозиции уже построенных примитивно рекурсивных функций.
Пример 8.9. Нигде не определенная функция ?(x).
Эта функция может быть задана, например, соотношением ?(x)= mu y[ s1(y)+x=0 ].
Отметим, что все функции в примерах 8.1 - 8.8 являются примитивно рекурсивными.

Содержание раздела