примитивной рекурсии и минимизации, примененные к функциям, имеющим рекурсивно перечислимый график, дают функции с рекурсивно перечислимым графиком. Так как все частично рекурсивные функции получаются посредством указанных операций из простейших функций о, S, 1т, ю1е1ощих согласно п. 4.4 примитивно рекурсивный график, то тем самым будет доказана и теорема 1. Болеетого, упомянутые утверждения относительно операций примитивной рекурсии и минимизации нам нет необходимости доказывать в общем виде. В силу результатов п. 3.4 достаточно будет рассматривать примитивные рекурсии и минимизации тех частных видов, которые указаны в п. 3.4.

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

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

G-i = {<hi .-MPin+i m

(i = 1, . . ., m),

где ai, Pjjt - подходящие примитивно рекурсивные функции. Нам надо изучить график F функции

/ [Ху, . . ., Хп) = g {gi (Xi, . . ., Хп), . . ., gm {Xi, . . ., Хп)).

Согласно определению операции суперпозиции утверждение (ху, . . ., Хп, у} (: F можно представить в виде

(Эг/1 . . . Ут){<Х1, .... Хп, 1/1> 6 Gi & . . .

... & <Xi, ...,Хп, Ут) 6 <?т & <У1, Уш, УУ £<?), (1)

где (3l/i . . . Ут) обозначает утверждение «существуют такие у, . . ., у, что. . .», а символ & обозначает слово и. В свою очередь, утверждение (1) с помощью графиков функций g, gi, . . ., gm можно персписать в виде

Шг... U(Pii (h) = Xi & ... & Pi„ (h) = Xn& ...

• • • & Pml (tm) = Xi & . . . & P,„„ {tj = Xn &

& «1 (ta) = Pi„ .1 (h)&...& (o) = Pmn+i iU & сст.г (io)=V)-

§ 6. Частично рекурсивные функции

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

6.1, Параметризация часггично рекурсивных функций. Согласно п. 4.4 графиком 7г-местной частичной функции / {ху, . . ., Хп) называется совокупность последовательностей (Xi, . . ., Хп, уУ натуральных чисел, удовлетворяющих соотношению

/ {ху, . . ., Хп) = у.

В частности, график нигде не определенной функции есть пустое множество.

Теорема 1{о графике частично рекурсивной функции). Для того чтобы частичная функция / была частично рекурсивной, необходимо и достаточно, чтобы график! был рекурсивно перечислим.

Для нигде не определенной функции / утверждение этой теоремы очевидно. Для функций с непустым графиком утверждение теоремы 1, как легко видеть, означает, что функция / {ху, . . ., Хг) тогда и только тогда частично рекурсивна, когда она представима в параметрической форме

Xi = ai (t) (i = 1, . . ., ll), у = P (t),

где at {t), p {t) ~ подходящие примитивно реку]:спвные функции. По этой причине теорему 1 пногда называют теоремой о параметрпческом представ л енпп частично рекурсивных функций.

Достаточность условий теоремы 1 устанавливается так же, как в и. 4.4. Доказательство необходимости удобно разбить на ряд самостоятельных утверждений. А именно, докажем последовательно, что операции подстановки.

Поэтому условие (х, у, zy £ F2 равносильно существованию чисел ty, «2, . . ., ty, для которых

а (t,) = х, а (4) = Р (tx), . . ., а (t„) = Р Р (ty) = z.

т. е. для которых

\a{ti)-x\ + S fe(im)-P(ii) + P(y-zl = 0.

в п. 3.3 была построена примитивно рекурсивная функция Гёделя Г (и, х) и было- показано, что для любых fj, . . ., ty система уравнений

Г (и, i) = ti (i = 1, . . ., у)

идюет решения относительно и. Подставляя в (3) вдгесто ti выражение Т{и, i), получим уравнение

I а (Г (U, 1)) - а; I + (Г (и, i + 1)) -"Р (Г {и, i)) \ +

+ P(r(H,i/))-z = 0, .(4)

идгегощее решение и тогда и только тогда, когда (3) имеет решение (г, . . ., ty). Согласно п. 3.1 левая часть уравнения (4) есть придштивно рекурсивная функция от х, у, Z, и. Обозначая ее через g {х, у, z, и), прнходшм к заключению, что совокупность состоит из всех тех троек (х, у, zy, для которых уравнение

g [х, у, z,u) = 0

ц.меет решение и. Так как функция g примитивно рекурсивна, то множество Fo рекурсивно перечислидю, что и требовалось.

В) Если частичная функция g {х, у) имеет рекурсивно перечисли.мый график, то функция / {х), получающаяся из g {х, у) операцией .иини.мизации:

f (х) = р„ [g {X, у) = 0), (5)

также и.меет рекурсивно перечисли.мый график.

Как и выше, дш можем предполагать, что график G функции g не пуст и, следовательно, пдгеет вид

G = {<а (t), (t), у (ф} (г = О, 1, . . .),

Поэтому, вводя функцию h{xi,...,Xn,y,to,...,t„,) = S I hj ih) (to) - Pi „.1 (ti) I + 1 ccm.i (to) - у i,

i, i i

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

(30- • • tn) {h (Xi, . . ., Xn, y, to, . . ., tj = 0).

Это означает, что график функции / состоит из всех тех последовательностей (х, . . ., х, уУ, для которых уравнение

h [хх, . . ., Хп, у, to, . . .,tj = 0

разрепшмо относительно to, . . .,t. Так как функция h примитивно рекурсивна, то на основании теоремы 1 из п. 4.4 заключаем, что график функции / рекурсивно перечислим.

Б) Если функция / (х, у) связана соотношениями

f{x,0)x, f{x,y + l)=h{f{x,y)) (2)

с функцией h, имеющей рекурсивно перечислимый график, то f [х, у) также имеет рекурсивно перечислимый график.

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

<а it), р (ф (f = О, 1, . . .),

где а, р - подходящие примитивно рекурсивные функции. График F функции / состоит из троек (х, у, z), для которых / [х, у) = Z. Разобьед! его на две части: совокупность Fy троек <а;, у, z), для которых i/ = О, и совокупность F2 троек (ж, у, zy, для которых г/ > 0. Первое из соотнЬше-ний (2) показывает, что F состоит из всех троек вида <а;. О, хУ и иотод1у Fj - рекурсивно перечислидтя совокупность. Остается показать, что совокупность F также рекурсивно перечислидш.

Соотношение (2) показывает, что условие (ж, у, z) ( б F2 равносильно существованию чпсел а, . . ., a„i таких, что

«1 = h {х), a=h . . .,z = h {uy,).

Равенство aii = h (a;) эквпва.чентно существованию числа fj+i, для которого

а (ti+i) = Яг, р (tui) = fli+i-

Полагая = Г {и, i), видим, что

(х, y}eF{3u) {h{x, у, и) = 0),

где через h {х, у, и) обозначено выражение, получающееся из левой части соотношения (7) подстановкой Г [и, i) вместо ti- Поскольку функция h примитивно рекурсивна, из (8) следует, что график F функции / рекурсивно перечислим.

Теорема 1 доказана. Отметим несколько ее следствий.

Следствие 1. Область определения каждой частично рекурсивной функции есть множество, рекурсивно перечислимое.

Действительно, еслп график частично рекурсивной функции f не пуст, то согласно теорел1е 1 его можно представить в виде

{<,щ {t), . . ., (ф},

где Ux{t), . . ., и,х (t) - примитивно рекурсивные функции. Но в таком случае областью определенпя функции / будет совокупность s-ok вида ( щ {t), . . ., щ (i)> (t = = О, 1, . . .) и потому эта область будет рекурсивно перечислимой.

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

в самом деле, если эта совокупность не пуста, то график функции моншо представить в указанно.л1 виде {щ {t), . . Us+1 {t)} И совокупностью всех значений функции / будет совокупность всех значений функции Usi (i). Так как функция Ug+i примитивно рекурсивна, то совокупность ее значений есть (п. 4.2) рекурсивно перечис-.шмое множество.

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

Следствие 3. Множество А п-ок чисел тогда и только тогда рекурсивно перечислимо, когда его частичная характеристическая функция частично рекурсивна.

Пусть А - непустое рекурсивно перечислимое множество. Оно состоит из п-ок вида (м (if), . . ., м„ (i)), где Ui {t) - примитивно рекурсивные функции. График частичной характеристической функции ф {х; . . ., а;„) множества А состоит из всех последовательностей вида <ui {t), . . .,Un {t), 0>, t = 0, 1, . . . Поскольку 0 = 0 {t)-примитивно рекурсивная функция, график ф {ху, . . ., х,) рекурсивно перечислим, а сама функция ф частично рекурсивна.

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

Следствие 4. ПустьЕ{хх, . . ., х, у, . . ., г/„) - частично рекурсивная функция от т -\- п переменных. Тогда совокупность А тех т-ок (Ху, . . ., х,„у, для которых уравнение

F {ху, . . ., х„„ Ух, . . ., Уп) = О

и.меет хотя бы одно решение (уу, . . ., г/„>, является рекурсивно перечислимы.и множеством.

Согласно теореме о парадютризацип график функции F, если он не пуст, можно представить в виде совокупностп последовательностей

<«! (О, . . ., ()> а,п+1 (0. • • м «,„+„ (i), а {t)y

{t = 0, 1,2, . . .),

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

g {х, i) = Ui (i = О, 1, • • у),

ajO (/ = О, 1, . . ., I/- 1), а„ - О,

т. е. равносильно утверждению о существовании чисел to, . . ty, для которых

а itj) = X, р {tj) = i, у (tj) ФО (j = 0,i, ...,у - 1),

а {ty) = X, р (g. = у,у {ty) = 0. (6) -

Условия (6) равносильны соотношению

и V-1

S (I ОС (ii) - а; I -Ы Р (f,) - i I) + у i П 7 (к) + У (ty) = 0.