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


Леммы о рекурсивных функциях


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

Лемма 8.1. Рекурсивность табличных функций. Пусть всюду определенная функция f(x) на всех аргументах, кроме конечного числа, равна некоторой константе c (такую функцию назовем табличной). Тогда она является примитивно рекурсивной.

Доказательство Пусть для функции f из условия леммы nf= max{x | f(x)

c}. Доказательство проведем индукцией по nf.

При nf=0 функция f является постоянной и поэтому примитивно рекурсивной (пример 8.1).

Предположим что все табличные функции g со значением ng

k примитивно рекурсивны и пусть nf = k +1 и f(0)=a. Определим табличную функцию f'(x) = f(x+1). Ясно, что nf' = k, и по предположению индукции f' примитивно рекурсивна. Легко проверить, что тогда f задается следующей схемой:

\left \{ \aligned f&(0)= a, \\ f&(x+1)=\/g(x,f(x))=\/I^2_1(f^\prime(x),f(x)) \endaligned \right.

и, следовательно, также примитивно рекурсивна.

Покажем замкнутость класса ч.р.ф. (п.р.ф.) относительно операций суммирования и произведения.

Лемма 8.2. Суммирование и произведение. Пусть функция f(x1,…, xn, y) является частично (примитивно) рекурсивной. Тогда и функции Fn+1 и Gn+1, заданные следующими равенствами

 F(x_1,\ldots,x_n,y)= \sum_{i=0}^y f(x_1,\ldots,x_n,i),
 G(x_1,\ldots,x_n,y)= \prod_{i=0}^y f(x_1,\ldots,x_n,i),

является частично (примитивно) рекурсивными.

Доказательство Действительно, эти функции задаются следующими примитивно рекурсивными схемами:

\left \{ \aligned F&(x_1,\ldots,x_n,0)= f(x_1,\ldots,0) \\ F&(x_1,\ldots,x_n,y+1)=\/F(x_1\ldots,x_n,y)+ f(x_1,\ldots,x_n,y+1) \endaligned \right.
\left \{ \aligned G&(x_1,\ldots,x_n,0)= f(x_1,\ldots,0) \\ G&(x_1,\ldots,x_n,y+1)=\/G(x_1\ldots,x_n,y)\times f(x_1,\ldots,x_n,y+1) \endaligned \right.

Приведем примеры использования леммы 8.2.

Пример 8.10. max_deg_div(x,y) = максимальная степень x, на которую нацело делится y.

Пусть exp(x,y) - экспоненциальная функция: exp(x,y) = xy. Ее примитивную рекурсивность легко установить, используя функцию умножения (см. задачу 8.1 (а) ). Тогда нетрудно проверить, что искомая функция задается соотношением

max\_deg\_div(x,y) = \sum_{i=0}^y \overline{sg}(rm(exp(x,i), y)) \dot{-} 1

и, следовательно, является примитивно рекурсивной.

Пример 8.11. Ограниченная минимизация. Пусть примитивно рекурсивная функция g(x,y) такова, что для каждого x найдется y

x, для которого g(x,y) =0. Положим F(x) = mu y [g(x,y) = 0].

Тогда, по определению, F(x) является частично рекурсивной функцией.


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



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