на самом деле, она примитивно

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

. По лемме 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) устанавливается непосредственно (см.

Содержание Назад Вперед