Дискретка

При n = 1 положим c(1)1 (x) = d(1)(x) = x. Рассмотрим случай n = 2.

Поскольку этот случай наиболее важный и часто встречающийся, мы будем использовать вместо c(2)1 , c(2)2 более простые обозначения c1, c2.

Функция d(2)(x; y) = [(x + y)(x + y + 1)=2] + x примитивно рекур-

сивна. Для построения функций c1, c2 определим вспомогательную функцию h(z) = ( tT )(z) 1, ãäå T (t; z) = sgn((t2 + t) 2z). Иначе говоря, h(z) наибольшее число, такое что [h(z)(h(z) + 1)=2] z.

Функция h(z) получена минимизацией из примитивно рекурсивной функции T (t; z), и, поскольку h(z) z, эта минимизация ограни- ченная. Таким образом, h(z) примитивно рекурсивная функция.

Тогда и функции c1(z) = z [h(z)(h(z) + 1)=2]; c2(z) = h(z) c1(z)

примитивно рекурсивны. При этом

d(2)(c1(z); c2(z)) = [(c1(z) + c2(z))(c1(z) + c2(z) + 1)=2] + c1(z) = = ([h(z)(h(z) + 1)=2] + z) [h(z)(h(z) + 1)=2] = z:

Далее, для любых x; y 2 N0

(x+y)(x+y+1)=2 d(2)(x; y) = (x+y)(x+y+1)=2+x

(x+y)(x+y+1)=2+(x+y) < (x+y+1)(x+y+2)=2;

èпотому h(d(2)(x; y)) = x + y. Следовательно,

c1(d(2)(x; y))=d(2)(x; y) [(x+y)(x+y+1)=2]=x; c2(d(2)(x; y))=y:

Отметим, что функции d(2), c1; c2, которые мы только что опре-

делили, имеют простой смысл: они осуществляют перечисление целочисленных точек плоскости с неотрицательными координатами по прямым x + y = b, то есть в следующем порядке: (0,0), (0,1), (1,0),

Из последнего определения, в частности, следует, что c(in)(y) является примитивно рекурсивной функцией не только от y, но и от n и i.

11. Функция Г¼деля. Наряду с координатными функциями, нам понадобится и так называемая функция Г¼деля (x; y). Примитивно рекурсивная функция двух аргументов (x; y) называется функци-

ей Г¼деля, если для любого m и любого набора a0; a1; : : : ; am 2 N0 существует число t 2 N0, такое что

(t; 0) = a0; (t; 1) = a1; : : : ; (t; m) = am

41

Например, функцией Г¼деля является определенная выше функция exp(x; y): для любых a0; a1; : : : ; am 2 N0 è äëÿ t = pa0 pa1 pam

o 1 m будет

(t; m) = exp(m; t) = am :

x 10. Рекурсивно перечислимые множества

1. Определение рекурсивно перечислимого множества чи- сел.

Теорема 1. Пусть M непустое подмножество множества на- туральных чисел N0. Следующие условия равносильны:

(1)для некоторого n существует примитивно рекурсивная функция от n переменных f(x1; : : : ; xn), множество значений которой совпадает с M;

(2)существует примитивно рекурсивная функция f(x), множество значений которой совпадает с M;

(3)существует примитивно рекурсивная функция h(a; x), такая что уравнение h(a; x) = 0 имеет решение (относительно неизвестной x) тогда и только тогда, когда a 2 M;

(4)для некоторого n существует такая примитивно рекурсивная функция h(a; x1; : : : ; xn) от n+1 переменных, что уравнение h(a; x1; : : : ; xn) = 0 имеет решение (относительно неизвестных x1; : : : ; xn) тогда и только тогда, когда a 2 M.

Доказательство. (1))(2). Пусть f(x1; : : : ; xn) примитивно рекурсивная функция, множество значений которой совпадает с M; тогда множество значений функции g(x) = f(c1(x); : : : ; cn(x)), ãäå c1; : : : ; cnкоординатные функции, тоже совпадает с M.

(2))(3). Пусть f(x) примитивно рекурсивная функция, множество значений которой совпадает с M; положим h(a; x) = jf(x) aj. Разрешимость уравнения h(a; x) = 0 равносильна существованию x 2 N0, такого что f(x) = a, то есть тому, что число a принадлежит множеству значений M функции f(x).

(3))(4) очевидно.

(4))(1). Пусть h(a; x1; : : : ; xn) примитивно рекурсивная функция, такая что уравнение h(a; x1; : : : ; xn) = 0 разрешимо относительно x1; : : : ; xn тогда и только тогда, когда a 2 M. Выберем произвольный элемент b 2 M и положим

f(x; x1; : : : ; xn) = x sgn(h(x; x1; : : : ; xn)) + b sgn(h(x; x1; : : : ; xn)):

42

Если a 2 M, то уравнение h(a; x1; : : : ; xn) = 0 имеет решение x1; : : : ; xn, и для этих чисел будет

f(a; x1; : : : ; xn) = a 1 + b 0 = a:

Таким образом, множество значений функции f(x; x1; : : : ; xn) содержит M. Обратно, пусть a = f(x; x1; : : : ; xn) принадлежит множеству значений функции f(x; x1; : : : ; xn). Åñëè h(x; x1; : : : ; xn) = 0, òî

a=x sgn(h(x; x1; : : : ; xn))+b sgn(h(x; x1; : : : ; xn))=x 1+b 0=x

принадлежит M, так как существует решение x1; : : : ; xn уравнения h(x; x1; : : : ; xn) = 0; åñëè æå h(x; x1; : : : ; xn) 6= 0, òî

a=x sgn(h(x; x1; : : : ; xn))+b sgn(h(x; x1; : : : ; xn))=x 0+b 1=b 2 M:

Теорема полностью доказана.

Подмножество M множества N0 называется рекурсивно перечис-

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

2. Рекурсивно перечислимые подмножества декартовых сте-

пеней N0. Подмножество M декартовой степени Nn0 множества на- туральных чисел называется рекурсивно перечислимым, если подмножество

M0 = fd(n)(a1; : : : ; an) j (a1; : : : ; an) 2 Mg

множества N0 рекурсивно перечислимо (здесь, как и раньше, через d(n) обозначается примитивно рекурсивная функция, нумерующая

точки из Nn0 ).

Теорема 2. Пусть M непустое подмножество Nn0 ; следующие условия равносильны:

(1)M рекурсивно перечислимо;

(2)для некоторого m существуют такие примитивно рекурсив-

ные функции f1(t1; : : : ; tm); : : : ; fn(t1; : : : ; tm), что M состоит из всех точек вида (f1(t1; : : : ; tm); : : : ; fn(t1; : : : ; tm)), ãäå t1; : : : ; tm независимо пробегают N0;

(3) существуют такие примитивно рекурсивные функции f1(t),

: : : ; fn(t), что M состоит из всех точек (f1(t); : : : ; fn(t)), где t пробегает N0;

(4) существует такая примитивно рекурсивная функция h(a1; : : : ; an; x), что уравнение h(a1; : : : ; an; x) = 0 имеет решение (относительно неизвестной x) тогда и только тогда, когда (a1; : : : ; an) 2 M;

(5)для некоторого m существует такая примитивно рекурсивная функция h(a1; : : : ; an; x1; : : : ; xm) от n + m переменных, что уравнение h(a1; : : : ; an; x1; : : : ; xn) = 0 имеет решение (относительно неизвестных x1; : : : ; xn) тогда и только тогда,

когда (a1; : : : ; an) 2 M.

43

Доказательство. Повторяя доказательство теоремы 1, мы получим равносильность условий (2)-(5); остается установить равносильность

(1) è (3).

(1))(3). Åñëè M Nn0 рекурсивно перечислимое множество, то, по определению, множество

M0 = fd(n)(a1; : : : ; an) j (a1; : : : ; an) 2 Mg

является рекурсивно перечислимым подмножеством N0 и потому сов-

падает с множеством значений некоторой примитивно рекурсивной функции f(t). Координатные функции c(1n); : : : ; c(nn) осуществляют от-

ображение N0 ! Nn0 , обратное к d(n); поэтому M это множество точек (f1(t); : : : ; fn(t)), где через fi(t) обозначены примитивно рекурсивные функции c(in)(f(t)) (1 i n).

(3))(1). Пусть M множество точек (f1(t); : : : ; fn(t)), где t пробегает N0, à f1(t); : : : ; fn(t) примитивно рекурсивные функции. Тогда множество M0 = fd(n)(a1; : : : ; an) j (a1; : : : ; an) 2 Mg представ-

ляет собой множество значений примитивно рекурсивной функции d(n)(f1(t); : : : ; fn(t)) и потому является рекурсивно перечислимым под-

множеством N0. Но это и означает, что множество M Nn0 сивно перечислимо.

3. Свойства рекурсивно перечислимых множеств. Покажем,

что объединение и пересечение конечного числа рекурсивно пере- числимых множеств рекурсивно перечислимы. Действительно, пусть fi(a1; : : : ; an; x) (1 i k) такие примитивно рекурсивные функ-

ции, что уравнение относительно x

fi(a1; : : : ; an; x) = 0

тогда и только тогда имеет решение, когда (a1; : : : ; an) 2 Mi. Функции

k

X

f(a1; : : : ; an; x1; : : : ; xk) = fi(a1; : : : ; an; xi);

i=1

k

Y

g(a1; : : : ; an; x1; : : : ; xk) = fi(a1; : : : ; an; xi)

i=1

примитивно рекурсивны, и уравнения

f(a1; : : : ; an; x1; : : : ; xk) = 0; g(a1; : : : ; an; x1; : : : ; xk) = 0

разрешимы относительно x1; : : : ; xk тогда и только тогда, когда набор (a1; : : : ; an) принадлежит соответственно пересечению и объединению множеств M1; : : : ; Mk.

44

x 11. Рекурсивные функции

1. Определение рекурсивных функций. В свойствах примитив-

но рекурсивных функций, приведенных в предыдущей главе, отсутствовало упоминание обратных функций. И это не случайно: обратная к примитивно рекурсивной функции, даже если она существует, не обязана быть примитивно рекурсивной.

При нашем подходе к определению рекурсивной функции мы будем пользоваться понятием графика функции. Пусть f(x1; : : : ; xn) некоторая функция; е¼ графиком называется подмножество

f(x1; : : : ; xn; f(x1; : : : ; xn)) j x1; : : : ; xn 2 N0g

множества Nn0 +1. Функция f(x1; : : : ; xn) называется рекурсивной (в другой терминологии общерекурсивной), если е¼ график рекурсивно перечислим.

Отметим простейшие свойства рекурсивных функций.

Всякая примитивно рекурсивная функция рекурсивна. Действительно, если f(x1; : : : ; xn) примитивно рекурсивная функция, то е¼ график множество всех точек (x1; : : : ; xn; f(x1; : : : ; xn)); но все координаты x1; : : : ; xn; f(x1; : : : ; xn) примитивно рекурсивные функ- öèè îò x1; : : : ; xn, и по теореме 2 это множество рекурсивно перечислимо.

Пусть f(x1; : : : ; xn) рекурсивная функция; е¼ график рекурсивно перечислим, и значит, существуют такие примитивно рекурсивные функции g1(t); : : : ; gn(t); g(t), что этот график состоит из то- чек (g1(t); : : : ; gn(t); g(t)). Значения аргументов x1; : : : ; xn независи- мо друг от друга пробегают N0 и определяют значение функции f; поэтому функции g1(t); : : : ; gn(t); g(t) обладают свойствами:

(1)для любых чисел x1; : : : ; xn 2 N0 найдется число t 2 N0, äëÿ которого g1(t) = x1; : : : ; gn(t) = xn;

(2)åñëè g1(t) = g1(t0); : : : ; gn(t) = gn(t0), òî g(t) = g(t0);

(3)f(g1(t); : : : ; gn(t)) = g(t) для любого t 2 N0.

Указанное только что представление рекурсивной функции будем называть е¼ примитивно рекурсивной параметризацией. Из существования параметризации легко следует, что всякая рекурсивная функция может быть получена из примитивно рекурсивных при помощи подстановки и единственный раз примененной операции минимизации. Действительно, пусть в предыдущих обозначениях

h(x1; : : : ; xn; t) = jg1(t) x1j + + jgn(t) xnj;

по свойству (1) уравнение h(x1; : : : ; xn; t) = 0 имеет решение при любых x1; : : : ; xn, так что функция ( th)(x1; : : : ; xn) определена, и по свойству (3)

f(x1; : : : ; xn) = g(( th)(x1; : : : ; xn)):

45

2. Подстановка для рекурсивных функций.

Теорема 1. Пусть f(x1; : : : ; xn), g1(y1; : : : ; ym), . . . , gn(y1; : : : ; ym) рекурсивные функции. Тогда функция

h(y1; : : : ; ym) = f(g1(y1; : : : ; ym); : : : ; gn(y1; : : : ; ym));

получающаяся из f подстановкой функций g1; : : : ; gn вместо пере- менных, тоже рекурсивна.

Доказательство. Пусть

= f(p1(t); : : : pn(t); p(t)) j t 2 N0g;i = f(qi1(si); : : : qim(si); qi(si)) j si 2 N0g

графики функций f, gi (1 i n) c примитивно рекурсивными компонентами pi; qij; p; qi. Для того, чтобы точка (a1; : : : ; am; b) принадлежала графику функции h, необходимо и достаточно, чтобы существовали такие t; s1; : : : ; sn è x1; : : : ; xn, ÷òî

qi1(si) = a1; : : : ; qim(si) = am; qi(si) = xi (1 i n)

(эти равенства означают, что gi(a1; : : : ; am) = xi),

p1(t) = x1; : : : ; pn(t) = xn; p(t) = b

(это значит, что f(x1; : : : ; xn) = b). Но эта система равенств равносильна одному уравнению

левая часть которого примитивно рекурсивная функция от b, t,

ai, sj, xj (1 i m, 1 j n). Таким образом, (a1; : : : ; am; b) 2

тогда и только тогда, когда наше уравнение разрешимо относительно t; s1; : : : ; sn; x1; : : : ; xn. По теореме 2 из x 10 это означает, что гра-

фик функции h рекурсивно перечислим, то есть сама функция h(y1; : : : ; ym) рекурсивна.

3. Минимизация для рекурсивных функций.

Теорема 2. Пусть f(x1; : : : ; xn; t) такая рекурсивная функция, что для любых x1; : : : ; xn 2 N0 существует решение t уравнения f(x1; : : : ; xn; t) = 0. Тогда функция ( tf)(x1; : : : ; xn) также рекурсивна.

Доказательство. Пусть = f(p1(s); : : : pn(s); p(s); q(s)) j s 2 N0g график функции f c примитивно рекурсивными компонентами pi; p; q. Для того, чтобы точка (x1; : : : ; xn; a) принадлежала графику функции tf, необходимо и достаточно, чтобы

f(x1; : : : ; xn; 0) 6= 0; : : : ; f(x1; : : : ; xn; a 1) 6= 0; f(x1; : : : ; xn; a) = 0:

46

Для этого необходимо, чтобы для i = 0; 1; : : : ; a существовали значе- ния параметра si, для которых

p1(si) = x1; : : : ; pn(si) = xn; p(si) = i; q(si) 6= 0; åñëè i < a; q(sa) = 0:

К сожалению, количество неизвестных si зависит от a; чтобы устранить это неудобство, используем функцию Г¼деля (s; i). Соглас-

но определению этой примитивно рекурсивной функции существует число s 2 N0, такое что (s; 0) = s0; (s; 1) = s1; ::; (s; a) = sa. Ïîä-

ставляя эти выражения в предыдущие равенства, преобразуем их к системе уравнений

p1( (s; i)) = x1; : : : ; pn( (s; i)) = xn; p( (s; i)) = i;

XX

+ jp( (s; i)) ij + jpj( (s; i)) xjj = 0;

i=0 j=1

левая часть которого примитивно рекурсивная функция от a, s, x1; : : : ; xn. Таким образом, (x1; : : : ; xn; a) принадлежит графику функции tf тогда и только тогда, когда наше уравнение разрешимо относительно s. По теореме 2 из x 10 это означает, что график рекурсивно перечислим, то есть сама функция ( tf)(x1; : : : ; xn) рекурсивна.

4. Примитивная рекурсия для рекурсивных функций.

Теорема 3. Пусть h(x1; : : : ; xn 1), g(x1; : : : ; xn 1; xn; xn+1) рекурсивные функции. Тогда функция f(x1; : : : ; xn), полученная из них примитивной рекурсией, также рекурсивна.

Доказательство. Пусть

= f(p1(s); : : : ; pn 1(s); p(s)) j s 2 N0g;

= f(q1(t); : : : ; qn 1(t); qn(t); qn+1(t); q(t)) j t 2 N0g

графики функций h; g c примитивно рекурсивными компонентами pi; qj, p; q. При a 6= 0 точки

(x1; : : : ;xn 1; 0; y0); (x1; : : : ;xn 1; 1; y1);

: : :

(x1; : : : ;xn 1; a; ya)

принадлежат графику функции f тогда и только тогда, когда

y0 = h(x1; : : : ; xn 1);

47

y1 = g(x1; : : : ; xn 1; 0; y0); y2 = g(x1; : : : ; xn 1; 1; y1);

: : :

ya = g(x1; : : : ; xn 1; a 1; ya 1);

то есть когда точка (x1; : : : ; xn 1; y0) принадлежит , а все точки (x1; : : : ; xn 1; i; yi; yi+1) (0 i < a) принадлежат . Для этого необходимо и достаточно существование таких s0; s1; : : : ; sa, ÷òî

p1(s0) = x1; : : : ; pn 1(s0) = xn 1; p(s0) = y0;

q1(si)=x1; : : : ; qn 1(si)=xn 1; qn(si)=i 1; qn+1(si)=yi 1; q(si)=yi

(1 i a). Исключая из этой системы величины y0; y1; : : : ; ya 1 è обозначая ya через b, находим, что точка (x1; : : : ; xn 1; a; b) принадлежит графику функции f тогда и только тогда, когда существуют числа s0; s1; : : : ; sa 2 N0, такие что

p1(s0) = x1; : : : ; pn 1(s0) = xn 1; p(s0) = qn+1(s1);

q1(si) = x1; : : : ; qn 1(si) = xn 1; qn(si) = i 1 (1 i a); q(si) = qn+1(si+1) (1 i < a); q(sa) = b:

Заменяя, как и выше, неизвестные si на (s; i), преобразуем эти равенства к системе уравнений

левая часть которого представляет собой примитивно рекурсивную функцию от a; b; s; x1; : : : ; xn 1. Таким образом, (x1; : : : ; xn 1; a; b) принадлежит графику функции f тогда и только тогда, когда наше

уравнение разрешимо относительно s. По теореме 2 из x 10 это озна- чает, что график рекурсивно перечислим, то есть сама функция f(x1; : : : ; xn) рекурсивна.

48

5. Другое описание класса рекурсивных функций. Соединяя

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

Теорема 4. Класс рекурсивных функций совпадает с классом функций, которые могут быть получены из элементарных функций o, s,

id, pr1, pr2 при помощи применения (вообще говоря, многократного) операций подстановки, примитивной рекурсии и минимизации.

Доказательство. В конце пункта x 11.1 было отмечено, что любая

рекурсивная функция получается минимизацией из примитивно рекурсивной функции, которая, в свою очередь, может быть получе- на из элементарных функция подстановками и примитивными рекурсиями. Таким образом, класс рекурсивных функций содержится в классе функций, которые могут быть получены из элементарных функций при помощи подстановок, примитивных рекурсий и минимизаций. Обратно, элементарные функции рекурсивны, и теоремы 1, 2 и 3 показывают, что подстановки, примитивные рекурсии и минимизации не выводят за пределы класса рекурсивных функций, который, таким образом, содержит класс функций, которые получаются из элементарных подстановками, примитивными рекурсиями и минимизациями.

6. Замечание о рекурсивно перечислимых множествах. Ра-

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

Теорема 5. Пусть M непустое подмножество Nn0 ; следующие условия равносильны:

(1)M рекурсивно перечислимо;

(2)для некоторого m существуют такие рекурсивные функции f1(t1; : : : ; tm); : : : ; fn(t1; : : : ; tm), что M состоит из всех точек вида (f1(t1; : : : ; tm); : : : ; fn(t1; : : : ; tm)), ãäå t1; : : : ; tm независи- мо пробегают N0;

(3)существуют такие рекурсивные функции f1(t), : : : ; fn(t), что M состоит из всех точек (f1(t); : : : ; fn(t)), где t пробегает

N0;

(4)существует такая рекурсивная функция h(a1; : : : ; an; x), что уравнение h(a1; : : : ; an; x) = 0 имеет решение (относительно неизвестной x) тогда и только тогда, когда (a1; : : : ; an) 2 M;

(5)для некоторого m существует такая рекурсивная функция h(a1; : : : ; an; x1; : : : ; xm) от n + m переменных, что уравнение

h(a1; : : : ; an; x1; : : : ; xn) = 0 имеет решение (относительно

49

неизвестных x1; : : : ; xn) тогда и только тогда, когда точка (a1; : : : ; an) принадлежит M.

Доказательство. Повторяя доказательство теоремы 2 из x 10, мы по-

лучим равносильность условий (2)-(5). То, что из (1) следует (3),

тривиально: по теореме 2 для рекурсивно перечислимого множества M Nn0 существуют даже примитивно рекурсивные функции f1(t),

. . . , fn(t), такие что M состоит из всех точек (f1(t); : : : ; fn(t)), t 2 N0. Заметим, что если f(x) рекурсивная функция и g(t), h(t) такие примитивно рекурсивные функции, что график функции f(x) состоит из всех точек вида (g(t); h(t)), то множество значений функции f(x) совпадает с множеством значений примитивно рекурсивной функции h(t) и потому является рекурсивно перечислимым подмно-

жеством множества N0. Пусть теперь f1(t); : : : ; fn(t) такие рекурсивные функции, что M = f(f1(t); : : : ; fn(t)) j t 2 N0g. Тогда множество

M0 = fd(n)(a1; : : : ; an) j (a1; : : : ; an) 2 Mg N0

является множеством значений рекурсивной функции одной переменной d(n)(f1(t); : : : ; fn(t)) и потому, как мы только что заметили,

является рекурсивно перечислимым подмножеством N0. Íî ýòî â òî÷- ности означает, что множество M Nn0 рекурсивно перечислимо. Таким образом, из (3) следует (1).

x 12. Рекурсия второй ступени

До сих пор у нас не было ни одного примера рекурсивных, но не примитивно рекурсивных функций; в следующих пунктах мы докажем существование таких функций.

ду множеством N0 и его декартовым квадратом.

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

f(0; 0) = a;

f(x; y) = g(x; y; f(c1('(x; y)); c2('(x; y))));

ãäå a 2 N0, g(x; y; z), '(x; y) примитивно рекурсивные функции, причем '(x; y) < d(2)(x; y). Нетрудно видеть, что функция f(x; y) кор-

ректно определена и примитивно рекурсивна. Действительно, функция h(z), определенная условиями

h(0) = a;

h(z) = g(c1(z); c2(z); h(('(c1(z); c2(z)))));

50