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

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

Лемма 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 задается следующей схемой:

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

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

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

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

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

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

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

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

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

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

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

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

. По лемме 8.2 эта функция примитивно рекурсивна. Пусть для данного x y0 = ? y [g(x,y) = 0]. Тогда при i < y0 имеем h(x,i) = 1, а при i

y0 h(x,i) =0. Поэтому искомая функция F задается равенством

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

Лемма 8.3. Кусочное задание или разбор случаев. Пусть h1(x1,…,xn), …, hk(x1,…,xn)- произвольные ч.р.ф., а всюду определенные ч.р.ф. f1(x1,…,xn), …, fk(x1,…,xn) таковы, что на любом наборе аргументов (a1, …, an) одна и только одна из этих функций равна 0. Тогда функция g(x1,…, xn), определенная соотношениями:

является частично рекурсивной.

Доказательство Действительно, gn можно представить как сумму k произведений:

Следующий класс функций, который нас будет интересовать, - это функции для однозначной нумерации пар и n-ок целых чисел и обратные им. Определим для любой пары чисел (x,y) ее номер c2(x,y)=2x(2y+1) - 1. Например, c2(0,0)=0, c2(1,0)=1, c2(0,1)=2, c2(1,1)=5, c2(2,1)= 19. Из единственности разложения чисел на простые множители следует, что функция c2: N2

N взаимно однозначно нумерует пары целых чисел. Нетрудно понять, что если c2(x,y) = z, то двоичная запись числа (z+1) имеет следующий вид: (двоичная запись y) 10x. Из такого представления можно однозначно извлечь значение x и значение y. Эти значения определяются следующими обратными функциями:

Из этих определений непосредственно следует, что для любого z выполнено равенство c2(c21(z), c22(z))=z.

Определим теперь по индукции функции cn нумерации n-ок чисел при n > 2 и обратные им координатные функции cni (1

n):

Из этих определений также непосредственно следует, что для любого z имеет место равенство cn(cn1(z), cn2 (z),…, cnn (z))=z. (Проверьте это свойство индукцией по n.)

Лемма 8.4. Рекурсивность нумерационных функций. Для любых n

2и 1

n все определенные выше функции cn и cni являются примитивно рекурсивными.

Доказательство Примитивная рекурсивность c2(x,y) устанавливается непосредственно (см.

задачу 8.1(а)). Функция c21(z) задается равенством c21(z)= max_deg_div(2,z+1) и является примитивно рекурсивной (это показано в примере 8.10). Для функции c22(z) справедливо определение c22(z) = div(2, div(2 c21(z)}, z+1) - 1) ( здесь мы используем примитивную рекурсивность функции целочисленного деления div(x,y) из задачи 8.1(e)). Примитивная рекурсивность остальных нумерационных функций следует по индукции из их определений (см. задачу 8.10).

В следующей лемме обобщается оператор примитивной рекурсии.

Лемма 8.5. (совместная рекурсия) Пpедположим, что фyнкции

in(x1,…,xn) (1 le i le k) и фyнкции ?in+k+1(x1, …, xn, y, y1, …, yk) (1

k) пpимитивно pекypсивны. Тогда фyнкции f1n+1(x1, …, xn, y), …, fkn+1(x1, …, xn, y), опpеделяемые следyющей совместной pекypсией

k) также являются пpимитивно pекypсивными.

Доказательство Обозначим чеpез

набоp пеpеменных x1,…,xn. Опpеделим следyющие пpимитивно pекypсивные фyнкции:

и положим

Фyнкция Fn+1 полyчена пpимитивной pекypсией из пpимитивно pекypсивных фyнкций и, следовательно, сама пpимитивно pекypсивна. Спpаведливость леммы тепеpь следyет из того, что для всякого

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