Леммы о рекурсивных функциях - часть 2

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

$h(x,y) = \prod_{i=0}^y sg(g(x,i))$

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

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

$F(x) = \sum_{i=0}^y h(x,i)$

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

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

$g(x_1,\ldots, x_n)= \left\{ \begin{array}{ll} h_1(x_1,\ldots, x_n), & \mbox{ если } f_1(x_1,\ldots, x_n)=0\\ h_2(x_1,\ldots, x_n), & \mbox{ если } f_2(x_1,\ldots, x_n)=0\\ \ldots \\ h_k(x_1,\ldots, x_n), & \mbox{ если } f_k(x_1,\ldots, x_n)=0\\ \end{array} \right.$

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

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

$g(x_1,\ldots, x_n)=h_1(x_1,\ldots,x_n) \overline{sg}(f_1(x_1,\ldots,x_n)) +\ldots\\ \hspace*{3cm}+ h_k(x_1,\ldots,x_n) \overline{sg}(f_k(x_1,\ldots,x_n)).\\$

Следующий класс функций, который нас будет интересовать, - это функции для однозначной нумерации пар и 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. Эти значения определяются следующими обратными функциями:

$c_{21}(z) =\textit{ максимальная\ степень\ 2,\ на\ которую\ делится}\ z+1 \mbox{ и }\\ c_{22}(z)=[( \textit{максимальное нечетное число, на которое делится}\ z+1) \dot{-} 1]/2.$

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

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

n):

$\qquad c_n(x_1,x_2,x_3,\ldots,x_n)=c_{n-1}(c_2(x_1,x_2),x_3,\ldots,x_n),\\ \qquad c_{n1}(z) = c_{21}(c_{(n-1)1}(z)),\\ \qquad c_{n2}(z) = c_{22}(c_{(n-1)1}(z)),\\ \qquad c_{n(i+2)}(z) = c_{(n-1)(i+1)}(z)\qquad (i=1,\ldots,n-2).$

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

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

2и 1

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

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

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