Дискретка

примитивно рекурсивна, а f(x; y) = h(d(2)(x; y)). Предыдущее по-

строение по существу использует полное упорядочение декартова ква- драта множества N0, причем получившееся вполне упорядоченное множество снова изоморфно N0. Однако, декартов квадрат множе- ñòâà N0 допускает и другие полные упорядочения, например, лекси-

кографическое. Будем обозначать лексикографический порядок на N20 символом :

(x; y) (z; t); åñëè x < z èëè x = z; y t:

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

Пусть '(x; y; z), (x; y; z), (x; y), (x; y) такие примитивно рекурсивные функции, что

далее, a 2 N0 и g(x; y; z; t) примитивно рекурсивная функция, и пусть f(x; y) такая функция, что

ãäå u = (x; y), v = (x; y).

Покажем, что функция f(x; y) полностью определена этими свой-

ствами. Точнее говоря, мы докажем более точное утверждение. Назовем набор точек (x; y) = (x0; y0) (x1; y1) (xm; ym) = (0; 0)

и чисел z0,z1,. . . ,zm вычисляющим значение функции f в точке (x; y), если для любого i, 0 i < m, существуют номера j; l > i, для кото-

ðûõ

(xi; yi) = xj; (xi; yi) = yj;

обратной индукцией по i находим, что из этих условий следует, что zi = f(xi; yi); в частности, значение функции f(x; y) = f(x0; y0) равно

z0. Мы утверждаем, что вычисляющие наборы есть для всех точек (x; y) 2 N20, и потому все значения функции f(x; y) однозначно опре-

делены наложенными условиями. Если бы это было не так, то, по- скольку множество N20 вполне упорядочено относительно лексикогра-

фического порядка, нашлась бы наименьшая пара (x; y), для которой нет вычисляющего набора; ясно, что (x; y) 6= (0; 0). Но пара (u; v) = ( (x; y); (x; y)) предшествует паре (x; y), поэтому для нее есть набор M с нужными свойствами. В частности, определено значение f(u; v). По нашему предположению, ('(x; y; f(u; v)); (x; y; f(u; v)) (x; y),

51

и потому для пары

('(x; y; f(u; v)); (x; y; f(u; v)))

тоже есть вычисляющий набор N. Но ясно, что объединение наборов M1 и N после перенумерации, располагающей все точки объединения в порядке возрастания, и добавления точки (x; y) и числа

g(x; y; f(u; v); f('(x; y; f(u; v)); (x; y; f(u; v))))

становится набором, вычисляющим значение функции f в точке (x; y),

а это противоречит предположению о том, что таких наборов не существует.

В описанной ситуации мы говорим, что функция f(x; y) получена рекурсией второй ступени при помощи функций g(x; y; z; t), '(x; y; z),

(x; y; z), (x; y), (x; y) при начальном условии f(0; 0) = a.

Теорема 1. Функция, полученная из примитивно рекурсивных функций рекурсией второй ступени, рекурсивна.

Доказательство. Пусть N30 график функции f(x; y). Из предыдущих рассуждений видно, что точка (x; y; z) принадлежит графику

тогда и только тогда когда существуют такие числа m, xi, yi, zi (0 i m), ÷òî x = x0, y = y0, z = z0 и для каждого i, 0 i m, существуют числа j, l, 0 j; k; l m, для которых

(xi; yi) = xj; (xi; yi) = yj;

Эти условия равносильны одному равенству

mm

X Y

jx x0j+jy y0j+jz z0j+ ( (j (xi; yi) xjj+j (xi; yi) yjj+

i=0 j;l=0

+j'(xi; yi; zj) xlj+j (xi; yi; zj) ylj+jg(xi; yi; zj; zl) zij)) = 0:

Заменяя, как и выше, переменные xi, yi, zi на (s; i), (t; i), (u; i), преобразуем это соотношение в равенство

jx (s; 0)j+jy (t; 0)j+jz (u; 0)j+

mm

XY

+( (j ( (s; i); (t; i)) (s; j)j+j ( (s; i); (t; i)) (t; j)j+

i=0 j;l=0

+j'( (s; i); (t; i); (u; j)) (s; l)j+j ( (s; i); (t; i); (u; j)) (t; l)j+ +jg( (s; i); (t; i); (u; j); (u; l)) (u; i)j)) = 0:

Обозначим левую часть этого равенства через h(x; y; z; m; s; t; u); яс-

но, что это примитивно рекурсивная функция. Таким образом, точка (x; y; z) принадлежит графику функции f(x; y) тогда и только то-

гда, когда уравнение h(x; y; z; m; s; t; u) = 0 с примитивно рекурсивной левой частью разрешимо относительно m, s, t, u. Следовательно,

52

график функции f(x; y) рекурсивно перечислим, и потому сама функция f(x; y) рекурсивна.

x 13. Функция, универсальная для класса примитивно рекурсивных функций

1. Нумерация примитивно рекурсивных функций. Напомним,

что любую примитивно рекурсивную функцию можно построить, исходя из элементарных функций o(x), s(x), id(x), pr1(x1; x2), pr2(x1; x2) при помощи подстановок и примитивных рекурсий. Процесс построения примитивно рекурсивной функции может быть закодирован в некотором алфавите, и, используя взаимно однозначное соответствие между словами в алфавите и натуральными числами, мы можем сопоставить нашей функции (точнее, процессу ее построения: одна и та же функция может быть получена из элементарных многими способами) некоторое натуральное число. Конечно, это можно сделать многими способами; здесь мы изложим один из вариантов такого со-

поставления. Существенную роль в нашей конструкции играют примитивно рекурсивные функции d(k)(x1; : : : ; xk), c(1k)(x),. . . , c(kk)(x) èç

x 9.10, осуществляющие взаимно обратные биекции

Nk0 ! N0; N0 ! Nk0 :

Напомним, что по нашему построению (см. x 9.10)

c(ik)(d(k)(x1; : : : ; xk)) = xi;

d(2)(d(k 1)(x1; : : : ; xk 1); xk) = d(k)(x1; : : : ; xk):

Каждому n 2 N0 мы сопоставим примитивно рекурсивную функцию fn(x) одной переменной. Сначала определим эту функцию для первых значений n:

f0(x) = o(x) = 0; f1(x) = s(x) = x + 1:

Пусть теперь n > 1 и примитивно рекурсивные функции fm(x) уже определены для всех m < n. По основной теореме арифметики число n однозначно представляется в виде произведения

1

Y

n = pikk ;

k=0

ãäå ik = 0 для всех k, кроме конечного числа, но хотя бы один из

этих показателей степени отличен от 0. Если r = i0 1, òî åñòü åñëè n = 2r3i1 : : : pirr+1+1 : : :, то положим

fn(x) = fi1 (d(r)(fi2 (x); : : : ; fi1+r (x))):

Åñëè i0 = 0, íî i1 1, òî åñòü n = 3i+15j : : : pirr (i 0, j 0, r 2), то в качестве fn(x) возьмем функцию, получающуюся следующей примитивной рекурсией:

fn(d(2)(x; 0)) = fi(x);

53

fn(d(2)(x; y + 1)) = fj(d(2)(d(2)(x; y); fnd(2)(x; y))):

Åñëè i0 = i1 = 0, i2 = 1; 2; 3, то в качестве функции fn(x) возьмем соответственно функции id(x), c1(x), c2(x). Во всех остальных случаях (то есть при i0 = i1 = 0 è i3 = 0 èëè i3 > 3) положим fn(x) = o(x) = 0.

Теорема 1. Для любой примитивно рекурсивной функции g(x) найдется номер n 2 N0, такой что g(x) = fn(x) äëÿ âñåõ x 2 N0.

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

обозначим через fnk следующую функцию k переменных:

fnk(x1; : : : ; xk) = fn(d(k)(x1; : : : ; xk)):

Мы будем доказывать следующее утверждение:

Для любой примитивно рекурсивной функции g(x1; : : : ; xk) от k переменных найдется номер n 2 N0, такой что

g(x1; : : : ; xk) = fnk(x1; : : : ; xk)

äëÿ âñåõ x1; : : : ; xk 2 N0.

По определению, примитивно рекурсивная функция g(x1; : : : ; xk)

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

димся сначала, что оно верно для элементарных функций:

Пусть теперь g(x1; : : : ; xk) = h(q1(x1; : : : ; xk); : : : ; ql(x1; : : : ; xk)) и пусть уже найдены такие номера j, i1,. . . , il, ÷òî

h(y1; : : : ; yl) = fjl(y1; : : : ; yl); qs(x1; : : : ; xk) = fiks (x1; : : : ; xk)

54

Пусть, наконец, функция g(x1; : : : ; xk) получена примитивной рекурсией

g(x1; : : : ; xk 1; 0) = h(x1; : : : ; xk 1);

g(x1; : : : ; xk 1; xk + 1) = q(x1; : : : ; xk 1; xk; g(x1; : : : ; xk 1; xk));

и пусть уже найдены такие номера i, j, что h(x1; : : : ; xk 1) = fik 1(x1; : : : ; xk 1);

q(x1; : : : ; xk 1; xk; y) = fjk+1(x1; : : : ; xk 1; xk; y):

Положим n = 3i+15j; тогда

fnk(x1; : : : ; xk 1; 0) = fn(d(k)(x1; : : : ; xk 1; 0)) =

= fn(d(2)(d(k 1)(x1; : : : ; xk 1); 0)) = fi(d(k 1)(x1; : : : ; xk 1)) =

= fik 1(x1; : : : ; xk 1) = h(x1; : : : ; xk 1):

Далее, обозначая для краткости t = d(k 1)(x1; : : : ; xk 1) и пользуясь тем, что d(k)(x1; : : : ; xk 1; y) = d(2)(d(k 1)(x1; : : : ; xk 1); y) = d(2)(t; y), находим:

fnk(x1; : : : ; xk + 1) = fn(d(k)(x1; : : : ; xk + 1)) =

=fn(d(2)(t; xk + 1)) = fj(d(2)(d(2)(t; xk); fn(d(2)(t; xk)))) =

=fj(d(2)(d(k)(x1; : : : ; xk 1; xk); fn(d(k)(x1; : : : ; xk 1; xk)))) =

=fj(d(k+1)(x1; : : : ; xk; fnk(x1; : : : ; xk))) =

=fjk+1(x1; : : : ; xk; fnk(x1; : : : ; xk)) = q(x1; : : : ; xk; fnk(x1; : : : ; xk)):

Таким образом, функция fnk(x1; : : : ; xk 1; xk) получена той же примитивной рекурсией, что и функция g(x1; : : : ; xk 1; xk), и потому эти две функции совпадают. Теорема полностью доказана.

2. Универсальная функция для класса примитивно рекур-

сивных функций. Рассмотрим теперь функцию двух аргументов U(x; y), определенную равенством U(x; y) = fx(y). Как следует из

предыдущей теоремы, для каждой примитивно рекурсивной функции одной переменной g(x) существует число n 2 N0, такое что

g(x) = U(n; x) для любого x 2 N0. Таким образом, все примитивно рекурсивные функции легко получаются из одной функции двух переменных U(x; y), и потому естественно называть функцию U(x; y)

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

Теорема 2. Функция U(x; y) рекурсивна.

Доказательство. Из рассуждений предыдущего пункта видно, что построение функции U(x; y) очень похоже на рекурсию второй сту-

пени; однако, если при нашем определении рекурсии второй ступени для вычисления значения функции в точке (x; y) требовалось

знать ее значение только в двух точках, то для вычисления значения

55

U(x; y) = fx(y) в некоторых случаях (например, при подстановке) требуется знать значения функции U в нескольких точках, предшествующих (x; y), причем количество этих точек зависит от (x; y). Мы обойдем эту трудность, заменив функцию U(x; y) тесно связанной

x

с ней функцией V (x; y) = Q pUi (i;y). Докажем, что функция V (x; y)

i=0

может быть построена рекурсией второй ступени и поэтому она рекурсивна; утверждение теоремы немедленно следует отсюда, так как функция U(x; y) = exp(x; V (x; y)) получается подстановкой в прими-

тивно рекурсивную функцию exp(x; z) на место второго аргумента рекурсивной функции V (x; y). В процессе доказательства нам будет удобно использовать две вспомогательные функции.

w(k; x; z) = d(k+1)(exp(exp(2; x)); z); : : : ; exp(exp(k + 2; x); z);

q(y) = d(2)(c1(y); c2(y) 1):

Лемма 1. Функция w(k; x; z) примитивно рекурсивна как функция от k, x, z. Функция q(y) примитивно рекурсивна; при этом если c2(y) > 0, òî q(y) < y.

Доказательство. Функция w(k; x; z) получается примитивной рекурсией

w(0; x; z) = exp(exp(2; x); z);

w(k + 1; x; z) = d(k+2)(exp(exp(2; x); z); : : : ; exp(exp(k + 3; x); z)) =

=d(2)(d(k+1)(exp(exp(2; x); z); : : : ; exp(exp(k + 3; x); z))) =

=d(2)(w(k; x; z); exp(exp(k + 3; x); z)):

Очевидно что функция q(y) примитивно рекурсивна. Если c2(y) > 0, òî c1(y) + (c2(y) 1) < c1(y) + c2(y). Напомним, что определенные в x 9.10 координатные функции нумеруют пары натуральных чисел

так, что пара с меньшей суммой координат всегда предшествует паре с большей суммой координат; поэтому номер

q(y) = d(2)(c1(y); c2(y) 1)

ïàðû (c1(y); c2(y) 1) строго меньше номера y = d(2)(c1(y); c2(y)) ïàðû

(c1(y); c2(y)).

Вернемся к доказательству того, что функция V (x; y) строится рекурсией второй ступени. Для этого надо построить примитивно ре-

56

где u = (x; y), v = (x; y). Мы зададим эти функции кусочно, разбив всю область задания на несколько областей.

Случай 1: x = 0. Ясно, что V (0; y) = 2U(0;y) = 2f0(y) = 20 = 1, и можно положить (0; y) = (0; y) = '(0; y; z) = (0; y; z) = 0, g(0; y; z; t) = 1.

Пусть теперь x 1; во всех оставшихся случаях (x; y) = x 1,(x; y) = y. Заметим, что при x 1 справедливо соотношение

V (x; y) = V (x 1; y)pUx (x;y) = V ( (x; y); (x; y))pfxx(y);

и потому нам достаточно указать такие функции '(x; y; z), (x; y; z), h(x; y; z; t), что выполняется следующее соотношение ( ):

fx(y) = h(x; y; V (x 1; y); V ('(x; y; V (x 1; y)); (x; y; V (x 1; y)))):

Случай 2: exp(0; x) > 0. Тогда x = 2k+13i1 5i2 : : : , ãäå is = exp(s; x),

k= exp(0; x) 1, è

fx(y) = fi1 (d(k+1)(fi2 (y); : : : ; fik+2 (y)) =

=fi1 (d(k+1)(exp(i2; z); : : : ; exp(ik+2; z)) = fi1 (w(k; x; z)) =

=exp(exp(1; x); V (x 1; w(exp(0; x) 1; x; V (x 1; y))));

где через z обозначено выражение V (x 1; y). Эта формула получа- ется из ( ), если положить

'(x; y; z) = x 1; (x; y; z) = w(exp(0; x) 1; x; z); h(x; y; z; t) = exp(exp(1; x); t):

Случай 3: exp(0; x) = 0, exp(1; x) > 0, c2(y) = 0. В этом и следующем случаях x = 3i+15j : : : , ãäå i = exp(1; x) 1, j = exp(2; x). Ìû

имеем:

fx(y) = fx(d(2)(c1(y); 0)) = fi(c1(y)) = exp(exp(1; x) 1; V (x 1; c1(y)));

что получается из ( ) при

'(x; y; z) = x 1; (x; y; z) = c1(y); h(x; y; z; t) = exp(exp(1; x) 1; t):

Случай 4: exp(0; x) = 0, exp(1; x) > 0, c2(y) > 0. Тогда fx(y) = fx(d(2)(c1(y); c2(y))) =

=fj(d(2)(d(2)(c1(y); c2(y) 1); fx(d(2)(c1(y); c2(y) 1))) =

=fj(d(2)(q(y); fx(q(y))))=exp(exp(2; x); d(2)(q(y); exp(x; V (x; q(y)))));

что совпадает с формулой ( ), если положить в ней

'(x; y; z) = x; (x; y; z) = q(y);

h(x; y; z; t) = exp(exp(2; x); d(2)(q(y); exp(x; t)):

57

Случай 5: exp(0; x) = exp(1; x) = 0. Тогда функция fx(y) совпадает с одной из элементарных функций от y:

Она на самом деле не зависит от z и t, и потому в качестве '(x; y; z), (x; y; z) можно взять любые функции, а в качестве h(x; y; z; t)

соответственно функции s(y), id(y), c1(y), c2(y), o(y).

3. Пример рекурсивной, но не примитивно рекурсивной функции. Рассмотрим функцию g(x) = sgn(U(x; x)). Поскольку функция U(x; y) рекурсивна, функция U(x; x), получающаяся из нее под-

становкоé, тоже рекурсивна, а вместе с ней рекурсивна и функция g(x) = sgn(U(x; x)). Но эта функция не примитивно рекурсивна:

если бы это было не так, то существовал бы номер n, такой что

g(x) = fn(x) = U(n; x), и мы имели бы U(n; n) = g(n) = sgn(U(n; n)), что невозможно.

x 14. Рекурсивные множества

1. Определение рекурсивного множества. Пусть A подмно- жество N0; напомним, что характеристической функцией множества A называется функция, определенная следующим образом:

Подмножество A множества N0 называется рекурсивным (примитивно рекурсивным) множеством, если функция A(x) рекурсивна (при-

митивно рекурсивна).

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

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

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

58

Теорема 1. Всякое примитивно рекурсивное множество рекурсивно, а всякое рекурсивное множество рекурсивно перечислимо. Существует рекурсивное, но не примитивно рекурсивное множество, и существует рекурсивно перечислимое, но не рекурсивное множество.

Доказательство. Если множество A примитивно рекурсивно, то его

характеристическая функция примитивно рекурсивна, а потому и рекурсивна; значит, множество A рекурсивно. Пусть теперь множе-

ство A рекурсивно. Тогда A можно охарактеризовать как множество

точек a 2 N0, таких что (a) = 1; но это множество совпадает с множеством тех a 2 N0, для которых уравнение j (a) 1j(x + 1) = 0 имеет решение. Следовательно, множество A рекурсивно перечислимо по теореме 5 из x 11.

В конце предыдущего параграфа мы пострîèëи рекурсивную, но не примитивно рекурсивную функцию g(x) = sgnU(x; x), принимаю-

щую только два значения 0 и 1; она является характеристической функцией множества

A = fa 2 N0 j g(a) = 1g;

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

Несколько сложнее построить пример рекурсивно перечислимого, но не рекурсивного множества. Пусть U(x; y) построенная в x 13

рекурсивная функция, универсальная для класса примитивно рекурсивных функций, и пусть A множество всех a 2 N0, таких что

уравнение jU(c1(a); t) aj + jU(c2(a); t)j = 0 разрешимо относительно t. Правая часть этого уравнения рекурсивная функция, поэтому по теореме 5 из x 11 множество A рекурсивно перечислимо. Покажем,

что оно не рекурсивно.

Предположим, что это не так. Тогда характеристическая функцияA(x) рекурсивна. Пусть f(t), g(t) такие примитивно рекурсивные функции, что график функции A(x) состоит из всех точек вида (f(t); g(t)); тогда A(f(t)) = g(t) для любого t 2 N0, и, поскольку функция A(x) определена на всем множестве N0, для всякого числа a 2 N0 найдется число t0 2 N0, такое что f(t0) = a.

Функции f(t), g(t) примитивно рекурсивны; поскольку функция U(x; y) универсальна для класса примитивно рекурсивных функций,

существует такие числа a; b 2 N0, что f(t) = U(a; t), g(t) = U(b; t) для любого t 2 N0. Пусть n = d(2)(a; b); тогда a = c1(n), b = c2(n).

Если n 2 A, то для всякого t 2 N0, такого что

U(c1(n); t) = U(a; t) = f(t) = n;

должно быть

U(c2(n); t) = U(b; t) = g(t) = A(f(t)) = A(n) = 1;

59

и потому числа jU(c1(n); t) nj, jU(c2(n); t)j не могут одновременно обращаться в 0, то есть уравнение jU(c1(n); t) nj+jU(c2(n); t)j = 0 не имеет решения. Это значит, по определению множества A, что n 2= A.

Обратно, пусть n 2= A. Существует такое число t0 2 N0, ÷òî f(t0) = n, è äëÿ íåãî

jU(c1(n); t0) nj + jU(c2(t0))j =

= jU(a; t0) nj + jU(b; t0)j = jf(t0) nj + jg(t0)j = 0;

потому что g(t0) = A(f(t0)) = A(n) = 0. Следовательно, уравнение jU(c1(n); t) nj + jU(c2(n); t)j = 0

имеет решение t0, а это означает, что n 2 A.

В обоих случаях мы пришли к противоречию, которое показывает, что предположение о рекурсивности множества A было ошибочно.

3. Свойства рекурсивных множеств.

Теорема 2. Объединение и пересечение конечного числа рекурсивных (примитивно рекурсивных) множеств рекурсивно (примитивно рекурсивно). Дополнение рекурсивного (примитивно рекурсивного) множества рекурсивно (примитивно рекурсивно).

Доказательство. Пусть множества A1,. . . ,An рекурсивны (прими-

тивно рекурсивны). Тогда функции A1 (x), . . . , An (x) рекурсивны (примитивно рекурсивны). Но характеристическими функциями объединения и пересечения множеств A1,. . . ,An и дополнения множества

A1 являются функции

nn

XY

и эти функции тоже рекурсивны (примитивно рекурсивны). А это и означает, что объединение и пересечение множеств A1,. . . ,An è äî- полнение множества A1 рекурсивны (примитивно рекурсивны).

Заметим, что дополнение рекурсивно перечислимого множества не обязано быть рекурсивно перечислимым. Действительно, пусть множество A и его дополнение B оба рекурсивно перечислимы. Тогда

существуют примитивно рекурсивные функции f(x), g(x), множествами значений которых являются соответственно множества A, B. Положим T (x; y) = jf(x) yjjg(x) yj; поскольку любое число y 2 N0 принадлежит в точности одному из множеств A, B, в точности одно из уравнений jf(x) yj = 0, jg(x) yj = 0 разрешимо, а значит, уравнение T (x; y) = jf(x) yjjg(x) yj = 0 разрешимо относительно

x при любом y, и потому определена функция h(y) = ( xT )(y), è ýòà

функция рекурсивна. Ясно, что харакòåðистической функцией множества A будет рекурсивная функция sgnjf(h(y)) yj, а это означает,

что множество A рекурсивно. Но, как мы видели выше, бывают рекурсивно перечислимые, но не рекурсивные множества; приведенное

60