h{xt, ..., хМ

= f,{xi,..., Xs), если g„ {xi,...,x,) = 0, не определено для остальных Х\,. . ., ж,

то h - также частично рекурсивная функция.

В силу теоремы о графике достаточно показать, что график Н функции h рекурсивно перечислим. Обозначим через Ai совокупность тех последовательностей (х, . . . . . ., Xs, уУ, которые удовлетворяют уравнениям

I fi [Ху, . . Xs) - у \ + gi {Ху, . . ., Xs) = О,

j = !,...,«. (4)

Ясно, что Н есть объединение совокупностей .i, . . ., А. Левая часть уравнения (4) есть частично рекурсивная функция от переменных Ху, . . ., ж, у. Поэтому в силу следствия 5 теоремы 1 (п. 6.1) мнонество Ai рекурсивно перечислимо. Из рекурсивной перечислимости множеств Ау, . . ., An вытекает рекурсивная перечислимость их объединения II, что и требовалось.

Следствие 1. Если область определения М частично рекурсивной функции f (ж, . . ., ж) рекурсивна, то f ижет рекурсивное доопределение.

По условию характеристическая функция х лшожества М общерекурсивна. Рассмотрим функцию g, заданную схемой

g{Xi, . . .,Xs) =

f {xi, . . ., Xs), если X(1. .,Xs) = 0, 0, если \xixi,. .., Xs) - i\ = 0.

Эта функция всюду определена и согласно предыдущей теореме частично рекурсивна. В то же время она является расширением функции /.

Следствие2. Если частично рекурсивная функция и [xq, Ху, . . ., Xs) является универсальной для совокупности всех s-жстных частично рекурсивных функций, то область определения М этой функции есть нерекурсивное рекурсивно перечислимое, множество.

Действительно, множество М как область определения частично рекурсивной функции рекурсивно перечислимо. Еслп бы J/ оказалось рекурсивным, то согласно следствию

1 функция f/была бы рекурсивно доопределимой, что противоречит теореме 1.

6.4. Исследование представления Клини. Ввиду важности нормального представления Клини (п. 6.2) представляет интерес более детальное исследование этого представления, произведенное Ску-лемом и Марковым. Прежде всего возникает вопрос: нельзя ли в представлении Клипп обойтись без внешней функции I. Полный отпет на этот вопрос дает

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

i{xy, . . ., Xs) = III (Q (х,.....Xs, t) = 0),

где Q (xi, . . ., Xs, i) - подходящая примитивно рекурсивная функция, необходимо и достаточно, чтобы график функции / был при.читивно рекурсивным.

Достаточность очевидна, так как примитивная рекурсивность графика / означает, что примитивно рекурсивна его характеристическая функция, равная "/ (Sj, . . ., Xs, у). Но тогда очевидное равенство

/ (a;i, . . ., Xs) = Иу (X {х„ . . ., Xs, у) = 0)

даст сразу же искомое представление / в виде (1).

Необходимость. Пусть / имеет вцд(1). Вводим функцию

G{xi, . . „х X) =

;.=0

Q ..., X, i)

В силу результатов п. 3.2 функция G примитивно рекурсивна. Кроме того, из формулы (2) видно, что у = f {ху, . . ., .т) тогда и только тогда, когда у - наименьший корень уравнения G (ж,, . . . • •> Xs, у) = 0. Следовательно,

/ (.ti, . . ., Xs) = ц, (G(.r,, . . ., Xs, t) = 0). (3)

Представление (3) имеет тот же вид, что и представление (1). Осо-ионность состоит в том, что теперь число / {ху, . . ., х = t является динственнбгм решением уравнения G (ху, . . ., Ж;, i) = 0. Но в таком слзчае функция sg G (ху, . . ., Xs, у) будет характерпстотескоп функцией графика / и, значит, этот график примитивно рекурсивен.

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

В качестве исходного материала берем построенщто в п. 5.2 оищерекурсивщто функцию D (.Го, Ху), универсальную для сово-к\л1ности всех одноместных примитивно рекурсивных функций. R качестве искомой функции можно взять ф>пакцпю

V {х) = Що (х, х).

Действительно, эта функция не может быть приоттивно рекурсивной, так как в противном сллчас для подходящего числа п мы "Мели бы тождество V (х) = D {п, х), из которого получили бы со-

тичная функция h {х, . . ., х) удовлетворяет условиям = h {хг, X,), если (xi, . . ., ж J = О, = /2 (1, • • •, Xs), если gi [ху, ...,Xs) = О,

отношение

D {п, п) = V (п) = SgD (п, п)

противоречащее определению функции sg. Характерпстпческой функцией графика v является функция

г {х, У) = sg\y - V {х) I .

Если бы эта функция была примптпвно рекурсивной, то такой же была бы и одноместная функция

X [х, 0) = V (X),

что противоречит доказанному выше. Таким образом, общерекурсивная функция V (х) не может быть представлена в форме Скуле-ма (1).

Чтобы получить характеристику тех функций L, которые могут играть роль «внешней» функции в теореме Клини о специальной форме (п. 6.2), введем, следуя Маркову [1], понятие функции большого размаха. Именно, будем говорить, что функция L {х) имеет большой размах, если для каждого натурального а уравнение L{x) =а имеет бесконечно много решений. Например, функцпя.,1и большого размаха являются ех„ж, х - \\[х и т. д.

Лемма 1. Для каокдой примитивно рекурсивной функции большого размаха L (х) существуют примитивно рекурсивная функция R {х) и общерекурсивная функция С [х, у), связанные тождествами

L {С {X, у)) = х, R{C (х, у)) = г/, C(L (х), R {х)) = г. (4)

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

По условию для каждого значения х уравнение L (у) = L (х) имеет бесконечно много решений относительно у. Пусть y,. г/,, у, . . .- эти решения, расположенные в иорядке возрастания. Среди них должно встретиться и само х: х = уп- Номер п б.удет функцией от х: п = R (х). Таким образом, у( = х. Из очевидной формулы

R{x)=Yч\L{x)-L{i)\i (5)

следует, что ф5нкцпя R {х) приьштпвно рекурсивна. Покажем теперь, что в последовательности

а (0), Л (0)>, а (1), R (1)>,..., а («), r («)>,... (6)

встречается каждая пара натуральных чисел п только один раз.

Действительно, из определения функции R (х) выводим, что номером произвольной пары чисел <а, Ь> в последовательности (6) служит решение уравнеппя L {х) = а, имеющее номер Ь.

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

С (х,у) = t{\x - L{t)\ + \y - R (t) I = 0) связана с функциями L л R тождествами (4).

Теорем а2 (Марков [1]). Если L {х) -- прим-итивно рекурсивная функция большого размаха, то для каждого s > О каждая s-местная частично рекурсивная функция f может быть представлена в виде

f (xi, . . .,xs)= L (lit {P (xi, . . ., Xs, t) = 0)),

где F - подходящая {зависящая от /) примитивно рекурсивная функция.

Если для какого-нибудь числа s О и какой-нибудь примитивно рекурсивной функции L {х) каждая з-.местная общерепурсивная функция f представима в клиниевской форме (7), то L (х) - функция большого размаха.

Докажем первое утверждение. Согласно лемме 1 существуют примитивно рекурсивная функция R [х) и общерекурспвная функция С {х, у), составляющие вместе с функцией L {х} тройку нумерующих функций. В таком случае согласно теореме Клини о нормальной форме (п. 6.2, замечание к теореме 1 каждая s-местная частично рекурсивная функция / может быть представлена в виде (7).

Второе утверждение будем доказывать способом от противного, а именно, покажем, что для каждой примитивно рекурсивной функции L {х), не имеющей большого размаха, существует общерекурсивная функция /, которую нельзя представить в виде (7). По усло-впю должно существовать такое число а, для которого уравнение L {х) = а имеет не более конечного числа решений. Если это уравнение совсем не имеет решений, то в виде (7) нельзя представить даже функцию / {х) = х. Допустим, что уравнение L {х) = а имеет решения bj, . . ., Ь,„, и пусть / (х) - какая-нибудь функция, имеющая вид (7). Как уже сказано, мы можем считать при этом, что для каждого X уравнение F {х, f) = О имеет не более одного решения t. Мы теперь хотим доказать, что ири сделанных предположениях совокупность решений уравнения / (.т) = а будет непременно примитивно рекурсивным мпожеством и, значит, никакая функция / {х), у которой множество решений заказанного уравнения не примитивно рекурсивно, не может быть представлена в виде (7). Но такую функцию построить очень легко. Наиримересли а = О, то

требуемым свойством обладает функция V {.г) = sg D (х, х). Если же а ф О, то требуемым свойством обладает функция aV {х).

Итак, рассмотрим решения уравнения / (ж) = а. Их совокупность есть объединение решений уравнений

lit {F (X, г) = 0) = Ъг (i = 1, . . ., т),

т. е. Зфавнешш F {х, Ъ{) = 0. Поскольку функция F {х, t) примитивно рекурсивна, то совокушность решенпй каждого уравнения F {х, bi) - О иртштивно рекзрспвпа (п. 4.1), а потому пртштпвно рекурсивной будет п совокупность решений уравнения f (х) = а, что и требовалось.

Дополненпя, примеры и задачи

1. Если график всюду определенной функции рекурсивен, то функция также рекурсивна. Существует не пргогативно рек5фсив-ная всюду определеннаяфункцпя, графпк которой примитивно рекурсивен (см. функцию"*!!, ((? = 0) в формуле (1) пз п. 6.4).

/ {хг, ., Хп) = \ii (g (ху, . . ., Хп, t) 0),

где g - подходящая общерекурсивная функция, когда график / рекурсивен. (Для доказательства необходимости заменить g в (а) функцией g*, для которой уравнение g* (х,, . . ., хп, t) = О имеет не более одного решения 1, после чего будем иметь / (Эс) = г/ <ф g* (Эе, у) = О, где положено 26 == ixy, . . ., а;„>.)

Частичная характеристическая функция множества М представима в виде (а) тогда и только тогда, когда М рекурсивно.

4. Элементарными по К а л ь м а р у [1] функциями называются всюду определенные функции от произвольного числа аргументов, которые можно полушть из функций 1, /Jjj, х -\- у, х у с помощью конечного числа операций подстановки, сушгирования и мультиплицированпя (см. п. 3.1).

Ясно, что все элементарные по Кальмару функции пртштивно рекурсивны. Обратное неверно. Пусть функция (а, п) определяется рекурсией g (а, 0) = 1, g (а, гг -- 1) = а""\ Показать, что каждая элементарная по Кальмару ф>нкция / (xj, . . ., х„) удовлетворяет неравенству

/ (xi, . . ., х„)< g (2 -L Xi -Ь . . . -1- х„, с),

где с - константа (зависящая от /). Отсюда, в частности, следует, что функция I (.г, у) пе элементарна (Б е р е ц к и [1]).

Верно лц, что каждая примитивно рекурсивная функция /, удовлетворяющая неравенству вида (Ь), элементарна?

5. Говорят, что фвкция / (xj, . . ., х„) полчается явной трансформацией из функции g (xj, . . ., Xm), если

/ (xi, . . ., х„) = («1, . . ., Urn),

где каждое и; - илп константа, или какая-то переменная xj. Говорят, что функция / (х,, . . ., х„, х) пол5чается пз ф\тачцпй g, h, а ограниченной рекурсией, еслп

/ (а-,., . . ., Хп, 0) = g (х,, . . ., Хп), f {ху, . . ., х„, X Ч- 1) = h (xj, . . ., Хп, X, f (xi, . . ., Хп, х)), / (xi, . . ., Хп, х) (xj, . . ., Хп, х).

Ппказать, что элементарные по Кальмару функция - это те и толь-1,п те функции, которые можно пол-чить из функций х -\- \, хЧ конечным число*! явных трансформаций и ограниченных рекурсий (Гжегорчик [1]).

6. Функцией, элементарной по С к у л е м у [3], называется

(уПКЦИЯ, которую можно получить из функций 1, /да, а: -Ь г/, X г/

111е])ацпями подстановки и сутшрования пз п. 3.1. Легко видеть, 4 10 функции .хг/, [х1у], I (х), г (х), Г (х, у) элементарны по Скулему. Никазать, что каждая элементарная по Скулему фзНКция / (х,, . . . , . ., х,г) удовлетворяет неравенству вида

/(xi, . . ., х„)< (2-f xi-Ь . . . -Ь,г„) ,че с - константа, зависящая от /. В частности, элементарные по

кальмару функции 2, 2 не элементарны по Скулему.

7. Класс некоторых общерекурсивнмх функций назовем "остаточным, если для любого п каждая неяустая рекурсивно пе-рочислимая совокупность ге-ок чисел является совокупностью гг-ок IIII да

<а, (г), . . ., а„ (<)> (г = О, 1, .-. .),

где «1 (/), . . ., а„ {t) - подходящие функции класса Например, -.авсдомо достаточным является класс всех примитивно рекурсивных функций,. Возникает задача о нахождении других, по возможности более простых и узких достаточных KniaccoB.

Анализируя доказательство теоремы о графике частично рекурсивной функции (и. 6.1), показать, что класс элементарных по (.1чулему функций является достаточным.

8. В каждом бесконечном рекурсивно перечпслпмом множестве <;iДержится бесконечное рекурсивное иодмйожество. С5тцеству1от бесконечные рекурсивно неречислимые мнониества, не содержащие м>сконечных прилштивно рекурсивных подмножеств (см. следующую •1адач5).

9. Пусть S( - совокупность значений функции Аккермапа

1 (х) из п. 5.3. Эта совокупность рекзфспвяа. Показать, что 21 не М(1жот быть совокупностью значений никакой при.митивно рекур-1 ивпой функции / (х), принимающей различные значения при различных значенпях аргумента. (Доп5стпм протпвное. Так как А (х) Ml 1И0Т0НН0 возрастает*), то на отрезке натурального ряда О, 1, . . .

., А {х) содержится ровно х чисел множества 2t- Берем числа

(0), / (1), . . ., / (х 1). Если они все лежат иа указанном отрезке, iii самое большое из них совпадает с А (х). Если нет, то casroe боль-

liioe из них больше А (х). Поэтому, полагая g (.г) == 2 У

"Меть Л (х) < g (х) для всех значеши"! т. Ввиду примитивной ре-«урсивностп функции g (х) указанное нераванство противоречит ос-ипвцому свойству ф5нкции Аккермапа - растп быстрее всякой ири--М11ТИВН0 рекурсивной фтакцпп.)

10. Пусть F, G - частично рекурспвньле одноместные функ-uiin, А - объединение областей оиределения! этпх функций. Показать, что определенная нпже функция Я пм(еет своей областью ои-

Для х>0; А(0) = А{1) = 2.

2. Обозначим через шш; (/ (х, t) = 0) наименьшее из решений t уравнения / (х, t) = О, если решения существуют. Еслп же решений нет, то значение указанного выражения будем считать неопределенным. Оператор miri; отличается от оператора мнпмизации [ij. Например,

(г - (г -- 1) = 0) не определено, min/ (/ - (ж + 1) = 0) = г -Ь 1.

Построить такую частично рекурсивную функцию / (х, t), для которой функция

g (х) = min, (/ (X, t) = 0)

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

3. Частичная функция / [ху, . . ., х„) тогда и только тогда представпма в форме