Xs) = О,

левая часть которого / есть частично рекурсивная функция от Xl, . . ., Xs, является рекурсивно перечислимым множеством.

В самом деле, функция

а {х) = (х -irt= 0)

частично рекурсивна и определена только для х = 0. Следовательно, совокупность решений уравнения (9) совпадает с областью определения частично рекурсивной функции сс (/ (ху, . . ., X,)). Согласно следствию 1 область определения этой функции рекурсивно неречислима, что и требовалось.

6.2. Универсальные частично рекурсивные функции. Установленная в предыдущем разделе теорема о параметризации позволяет легко доказать следующую важную тео-.рему Клини о нормальной форме.

Теорема 1. Каждая частично рекурсивная функция / {xi, . . ., ж,) представима в форме

/ {х„ . . .,х,) = 1 (fx, (F {х„ . . ., х„ t) = 0)), (1)

где I {х) - нумерационная функция из 7г. 3.3, а F - подходящая [зависящая omi) примитивно рекурсивная функция.

По условию график М флгнкцпп / рекурсивно перечислим и, следовательно (п. 4.4), существует примитивно рекурсивная функция g [х-, . . ., х, у, а), для которой

{ху, . . .,х„ууеМ =? (Эй) [g (.Ti, . . .,х„у,а) = 0).

Полагая с [у, а) = t, видим, что

(х„ .. .,х„у}е м

[Jt) [g [х„ ...,х„1 [t), г (t)) = о & I/ = г (t)). (2) в частности, если для каких-нибудь ж, . . ., х, t g[xx, . . .,x,,l {t),r [t)) = 0,

TO (xx, . . ., x„ I (ф 6 3£ II, значит, I [t) = / [x, . . ., x,),

TO есть

I (i.1, [g [x„ . . .,x„l [t), r [ф = 0)) = / [x„ . . ., X,).

Формула (3) доказана нами для тех значений х, . . . . . ., X,,, для которых левая часть равенства (3) имеет определенное значение. Но из (2) видно, что из неопределен-пости значения левой части формулы (3) вытекает неопределенность значения / [xi, . . ., Xs). Поэтому равенство (3) справедливо для произвольных значений х, . . ., х. Полагая

g [Хх, . . ., Xs, I (t), г [t)) = F [Хх, . . ., Xs, t),

получим формулу (1).

Замечание. Из доказательства формулы (1) видно, что в этой формуле вместо функции I [х) можно взять «ле-isyio)) функцию L (х) из любой тройки функций L (х), R [х), С [х, у), связанных с какой-нибудь нумерацией пар натуральных чисел (см. п. 3.3), лишь бы функции L [х), R [х) были примитивно рекурсивными.

До сих пор мы различали всюду определенные частично рекурсивные функции [рекурсивные функции) и общерекурсивные функции, т. е. функции, которые могут быть получены пз простейших функций о, s, операциями подстановки, прихмитивной рекурсии и операцией мини-mзaции, производимой лишь над такими функциями, для которых результат минидшзиции является всюду определенной функцией. Нам было лишь известно, что каждая оощерекурспвная функция рекурсивна. Верно и обратное утверждение.

Следствие. Каждая рекурсивная функция f общерекурсивна.

В самом деле, согласно теореме 1 функция / может быть представлена в форме (1), которая показывает, что функция / получается пз простейших функций операциями подстановки, пршштивной рекурсии и операцией минимиза-

где ОС; {t), а [t) - подходящие примитивно рекурсивные функции. Совокупность А состоит пз 7?г-ок (t), . . . . . ., оСт (i)>, где t пробегает совокупность решений уравнения а (t) = 0. Согласно п. 4.2 эта совокупность рекурсивно перечислима и потому либо пуста, либо является совокупностью значений подходящей примитивно рекурсивной функции р (и). Отсюда видно, что совокупность А либо пуста, либо состоит из всевозможных т-ок вида

(Р (и)), . . Ш (гг = О, 1, 2, . . .).

Так как функции at (Р (м)) примитивно рекурсивны, то совокупность А рекурсивно неречислима, ;что и требовалось доказать.

Следствие 5. Совокупность последовательностей (ж, . . ., Xs), удовлетворяющих уравнению

для всех значений Ху, . . ., Xs, t. Подставляя D+- (ay, Ху, Xs, t) вместо F (Xy, . . ., Xs, t) в формулу (1), получаем

f(xy, . . ., Xs) = r+i (a, Xy, . . ., Xs)

для всех значений Xy, . . ., х. Следовательно, функция [хо, Ху, . . ., Xs) универсальна для совокупности g-p..

6.3. Доопределение функций. Построение нерекурсивного рекурсивно перечислимого множества. Частичная функция g (ху, . . ., Xs) называется расширением частичной функции / (ху, . . ., Xs), если в калодой точке, в которой функция / определена, функция g также определена и значение g в этой точке совпадает с значением /, т. е. если график / содержится в графике g. Всюду определенное расширение частичной функции / называется доопределением f. Ясно, что каждая частичная функция имеет доопределение. Дело меняется, если.ищутся непроизвольные доопределения, а рекурсивные.

Теорема 1. Никакая частично рекурсивная функция и (xq, Ху, . . ., Xs), универсальная для совокупности всех s-местных частично .рекурсивных функций, не может иметь общерекурсивных доопределений.

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

Введем частичную функцию

V(x) =и(х,х, . . .,х). (1)

Эта функция частично рекурсивна и принимает лишь значения О и 1. Допустим, что она имеет рекурсивное доопределение W (х).

Рассматривая вместо W (х) s-местную функцию

n{W(Xy),Xi, . . .,Xs)=W{Xy)

п принимая во внимание универсальность функции U, впдцм, что для некоторого числа а и всех значений Ху, . . . ., Xs имеет место равенство

W (ху) = и (а, Ху, . . X,).

Полагая здесь Ху = . . . = х = а и сравнивая результат с соотношением (1), получаем противоречивое равенство

W{a) = W(a).

ции [Д., примененной единственный раз к функции F (ж, . . . . . x,t). Так как функция / по условию всюду определена, то функция

{F (х„ . . ., ж,, i) = 0)

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

Итак, понятия рекурсивной и общерекурсивной функции равносильны.

Рассмотрим теперь вопрос о построении универсальных функций. Пусть g-p.r обозначает совокупность всех «-местных частично рекурсивных функций. Как уже говорилось в п. 5.2, частичная функция U (хд, Ху, . . х) называется универсальной для совокупности р.г, если р.г состоит из функций

и (О, Ху, . . ., Xs), и (1, %, . . ., Xs), . . .

в п. 5.2 была построена общерекурсивная функция (п, Ху, . . ., х), универсальная для совокупности g-pr.r всех примитивно рекурсивных s-местных функций. Там же было показано, что универсальная функция для класса gpr-r не может быть примитивно рекурсивной, а универсальная функция для класса всех общерекурсивных s-местных функций не может быть рекурсивной. Однако для совокупности g-p.r частично рекурсивных функций положение иное.

Теорема 2. Существует частично рекурсивная функция Р+1 {xq, Ху, . . ., Xs), универсальная для совокупности всех s-местных частично рекурсивных функций.

А именно, такой функцией заведомо является частичная функция

{Хо, Ху, . . ., X,) = I (1-1, (Z)+2 (Жо, Ху,.. ., Xs, t) = 0)),

где D+ - упомянутая выше общерекурсивная функция, универсальная для совокупности всех (s -f- 1)-местных примитивно рекурсивных функций. Действительно, из формулы (4) непосредственно видно, что - частично рекурсивная (s -{- 1)-местная функция. С другой стороны, пусть f {ху, . . ., Xs) - какая-нибудь s-местная частично рекурсивная функция. Представляем ее в форме Клини (1). В этой форме функция F примитивно рекурсивна и, следовательно, найдется такое число а, что

F {ху, . . ., Xs, t) =Z)+2 {а, Ху, . . ., Xs, t)

in) = \l{Ii\u{t)-u{i)\фO

Число V [п) есть наименьшее значение t, для которого и (t){u (0), и (1), . . .,и (/г)}. Сравнивая это с определением функции g (х), видим, что

g{l) = u {V (0)), g{2) = u {V (и (0))), . . . Поэтому, вводя еще функцию w (х) посредством рекурсии w(0) =0,w(n+i.) = v {w (п)), (3)

окончательно будем пметь g (х) = и (w (х)) и, значит, в силу (2), (3) функция g (х) общерекурсивна.

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

Теорема 4. Если функции fi . . ., х) и а, (х-,, . . ., X,) {i = 1, . . ., п) частично рекурсивны и час-

Таким образом, функция V {х) не имеет рекурсивных доопределений И второе утверждение теоремы 1 доказано. Если бы частичная функция U (хд, х, . . ., Xg) имела рекурсивное доопределение Р [х, х-, . . х), то функция sg Р (х, X, . . х) в силу (1) была бы рекурсивным доопределением V (х), которое, как показано, не существует. Тем самым доказано и первое утверждение теоремы 1.

Теорема 2. Существуют нерекурсивные рекурсивно перечислимые множества.

Рассмотрим универсальную частично рекурсивную функцию (жц, х-х), построенную в п. 6.2. Вводим функцию

Е {х) = щТ {X, X).

Эта функция частично рекурсивна, принимает лишь значения О, 1 и не имеет рекурсивных доопределений. Обозначим через Мо совокупность решений уравнения Е (х) = = 0. Согласно следствию 5 теоремы о графике (п. 6.1) множество Жо рекурсивно перечислимо. Докажем, что оно не рекурсивно. Пусть, напротив, Mq рекурсивно. Тогда характеристическая функция % (х) множества Жо была бы рекурсивной. Но % (х) = О там, где Е (х) = О, ж % (х) = = 1 там, где Е (х) = I, т. е. % (х) - рекурсивное доопределение функции Е (х), которая таких доопределений не имеет. Полученное противоречие доказывает теорему.

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

Действительно, построенное выше множество Ж о рекурсивно перечислимо, но не рекурсивно. Поэтому оно непусто, а каждое непустое рекурсивно перечислимое множество есть совокупность значений подходящей примитивно рекурсивной функции g [х).

Примптпвно рекурсивные функции алгоритлшчески вычислимы. Следовательно, существует алгоритм, позво-.ЧЯЮ1ЦИЙ вычислить значенпе g [х) при любом х. В то же время нерекурсивность совокупности Жо всех значений функции g {х) означает, что не существует алгоритм, поз- * воляющий для произвольного чпсла а узнать, входпт а в Жо цлц нет, т. е. разрешимо уравнение g [х) = а или нет.

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

значений монотонно растущей общерекурсивной функции является рекурсивным множеством (п. 4.1, теорема 3).

Теорема 3. Каждое бесконечное рекурсивно перечислимое множество Л есть совокупность значений подходя-uieu общерекурсивной функции g (t), принимающей для различных значений t различные значения.

Иначе говоря, для каждого бесконечного рекурсивно перечислимого MHOoicecmea А существует общерекурсивная функция g [t), отображающая взаимно однозначно натуральный ряд на А.

По условию А есть совокупность значений некоторой примитивно рекурсивной функции и {t). Искомую функцию g (t) строим следующим образом. Полагая по определению g (0) = и (0). Пусть значения g (0), g (1), . . . . . ., g (п) уже определены. Тогда берем наименьшее t такое, что и (t) {g (0), g (1), . . ., g [п)}, и полагаем g (п -\- i) = и (t). Существование такого значения t вы-, текает из бесконечности множества А-. Поэтому функция g (п) всюду определена. Множество всех ее значений, очевидно, совпадает с множеством значений функции и. Для формального доказательства рекурсивности g выразим ее через и с помощью основных операций. Положим