х - у.

если а; > 1/,

[За; + г/ + 3, если х<у, является допустимой.

Согласно определению итерирования

ii(0) = 0, i.(l) = iO=.l, •(2) = s"il = 0,...,

то есть

fO, если X четно, если X нечетно.

Рассмотрим функцию

/ {х) = + [х12].

Так как

/ (0) = О, [YTlx)] = X

щхщх = {]ГЩ],

то из

/(а; + 1) = /(а;) + 2а; + 1 +

= f{x) + 2[\ff {X)] + 1 + sg [ {x)f F{f (x)),

F{t) = t + 2[Yt] + i +sg[YtP,

следует, что / получается итерированием функции F. Сог-гласно В) функция t + 2[уТ] допустима. С другой сто-

роны,

[f t? =t-g{t) = tq {t)

и потому функция [/7]2 также допустима. Но тогда допустима и функция F (t), а вместе с нею будут допустимы и функции

f{x) = x +

= f{x)~-xK

Наконец, из допустимости функций [а;/2] и ц) (t) = t + + 2 lYt] вытекает допустимость функций

2lft] = (t)t,[]/t] =

ху- 2

Остается доказать допустимость функции Для этого заметим сначала, что

ГО, если а;>г/,

И-У) + У) = [2а: + 2у + ?, еспшх<у,

и, значит, функция

Г1, если ху,

И..й = .8(((хй + й-х)={„

допустима. Но тогда допустима и функция X у = {х у) {х, 1у).

Д) Если g (ху, . . ., Хп)и h {xi, . . ., Хгг, у, z) - допустимые функции, то функция /, возникающая из g uh примитивной рекурсией:

t {xi, . . ., а;„,0) = g {xi, . . ., Хп), / [xi, . . ., Хп,у + i) (xi, . . ., a;„„ y, f [x, . . ., a;„, y)),

также допустима.

Согласно теореме 1 предыдугцего раздела функция / может быть получена из функций g, h, с, I, г, о, s, подстановками и рекурсией вида

Ф [х, 0) = ж, ф (ж, I/ -Ь 1) = Ф (ф (ж, у)), (1)

где Ф (z) - подходяш;ая суперпозиция функций g, h, о, s, Ii, с, I, г. Из ранее доказанного следует, что функции с, I, г, о, S, 1т допустимы И ЧТО суперпозиция допустимых функций Допустимая. Поэтому нам достаточно показать, что если функция Ф (z) допустима, хо функция ф (ж, у), связанная с Ф рекурсией (1), также допустима. Рассмотрим вспомогательные функции

v{x)=q ([/ж]), W (ж, у) = ((ж -f 2/)2 -Ь + X. (2) Из неравенств

(( + У) + У)< ((ж + у)- + у) + х<{{х-\-у)+у 1)2, (ж + у) < (ж + г/)2 + 1/< (.г + г/ -Ь 1)2

вытекает, что

q [w (ж, у)) = X, V {w (ж, у))=у.

определяемая схемой

Покажем, что если для некоторого х окажется q [х -\-+ \)Ф, то

(ж + 1) = 9- (z) + 1, v{x\) = v (х). (4)

В самом деле, условие q [х -\- i)0 означает, что х-\-1 не есть нолпый квадрат. Но тогда расстояние от ближайшего меньшего полного квадрата до а; -f 1 па 1 больше расстояния от этого квадрата до х, т. е. q (х 1) = д (х) -f -Ь 1. С друго1 стороны, так как х -\- i т есть полный квадрат, то [Ух + i.]=[Yх] и потому г; (х -- 1) = у (х)-

Теперь мы вместо функции ф(а:, у), определяемой рекурсией (1), введем функцию

Q{x) = q>{v [х), q{x)).

Из соотношений (3) получаем

8 (и; (у,х)) = <р(х, у).

Таким образом, функция ф {х, у) заведомо допустима, если допустима функция 6 (х). Посмотрим, какой рекурсивной схеме удовлетворяет 6 (х). Формулы (1), (2) дают 6 (0) = 0.

Далее , если q (х I) Ф О, то в силу (4)

6 (ж + 1) = ф (г; (х), q{x) + i) = 0 (6 {х)). Если же g (ж -Ь 1) = О, то

е (а; 4- 1) = ф (у {х + 1), 0) = v{x + 1). Поэтому для любых значений х Q{x + l) = ФiQ{x))sg{q{x + l)) +

+ v{x + i)sg {q {x + i)). Итак, вводя допустимую функцию 0 {X, Z) = Ф (Z) sg {q {X 4- 1)) + (а; + 1) Щ {q {х + 1)), мы можем рекурсивную схему для 6 {х) представить в впде 0 (0) = О, е (а; + 1) = в {х, В (х)). (5)

Согласно частному случаю теоремы 1 (п. 3.4) функция 6 (а;), удовлетворяющ;ая схеме (5), может быть получена пз допустимых функций Э, с, I, г, о, S, 1т подстановками и итерированием подходя1цей суперпозиции функций 0, с, I, г, о, S, Im- Такпм образом, функция 6 {х) допустима и утверждение Д) доказано.

Из утвернэдений А), Б), Д) неносредственно вытекает, ЧТО все примитивно рекурсивные функции допустимы.

В самом деле, каждая примитивно рекурсивная функция может быть получена из простейших функций конечным числом операций подстановки и примптивной рекурсии. Согласно Б) простейшие функции допустимы. Согласно А), Д) подстановки и примитивные рекурсии допустимых функций суть функции допустимые. Поэтому все примитивно рекурсивные функции допустимы и теорема доказана.

Теорема Р. Робинсона может быть изяш;но сформулирована на языке теории алгебр. Обозначим через % и gfpr. г совокупность всех одноместных частичных функций и соответственно совокупность всех одноместных примитивно рекурсивных функций. Алгебры

Ф = <5-;4-,*,«>, 5Ppr.r = <i5pr.r;4-,*,J>

называются алгебрами Робинсона. Теорема Робинсона означает, что совокупность 2fpr.r порождается функциями s,qQ, помош;ыо операций 4-, *, или, что то же самое, что подалгебра фрг. г порождается В ф элементами s и q.

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

Обобш;енная теорема Р. Робинсона. Те и только те частичные одноместные функции примитивно рекурсивны относительно произвольно заданной системы © одноместных частичных функций, которые можно получить из функций системы © и функций s, q конечнъш числом операций +, *, J.

Доказательство, изложенное выше для теоредш Р. Робинсона, остается верным и для обобш;енной теоремы Р. Робинсона, если в нем всюду слово функция заменить словами частичная функция, а слова примитивно рекурсивная заменить словами примитивно рекурсивная отно-сите.гъно ©.

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

местных частичных функций @, является совокупностью, порожденной системой В и функциями s, q с помощью операций +, *, J.

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

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

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

3. Пусть i/"2 = До. Oli ... а„ ... - разложение числа 1/2 в бесконечную десятичную дробь. Показать, что Оп есть примитивно рекурсивная функция от га.

4. Показать, что [х \Г2], [е] суть примитивно рекурсивные функции от X.

5. Показать, что функции /i, f, онределяемые посредством совместной рекурсии вида

h (0) = %, и (0) = а„

h + 1) = К (г, h (), /2 (г)), и + 1) = К к h ())

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

6. Располагаем все пары натуральных чисел в следующем порядке:

<0, 0>; <0, 1>, <1,0>, <1, 1>; <0, 2>, <2, 0>, <1, 2>, <2, 1>,

<2,2>; ...

Доказать, что номер С {х, у) = z пары (х, у> в этой последовательности и соответствующие функции х = L (z), = i? (z) примитивно рекурсивны.

7. Обозначим через % совокупность всех частичных функцпп двух переменных. На определяем операции] J посредством формул

(/ + g) (г, у) = f{x,y)+ g (х, у), if . g) {х, у) = f{x,g (г, у)), (X, 0) = О, f- {x,y+i)=f [у, f [х, у)). Доказать следующий аналог теоремы Р. Робинсона: двуместная функция / тогда п только тогда примитивно рекурсивна относительно произвольной системы двуместных частичных функций ®, когда / можетбыть получена конечным числом операций -{-, *,J из функций системы © и функций 1\, s (/j), q

8. Согласно теореме Р. Робинсона алгебра фргг = <5рг.г; -Ь, *,tf> порождается парой фз-икцип s, q. Показать, что алгебра фру J порождается и парой фнкцпп s, I (таюке парой s, г), где I, г - канторовы функцпп из п. 3.3 (см. Р. Робинсон [1]).

9. Вводим бинарн\то операцию v над одноместными функциями, полагая по определению (/vg) {х) = с (f (х), g [х)). Показать, что

алгебра <5ргг; *> порождается парой функций s, I (и парой г, S) (Р. Робинсон [1]).

10. Алгебра <5рг.г; порождается парой подходящих

функций и не порождается никакой одной функцией из gj.. (10. Р о б ИИ с о и [1]).

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

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

4.1. Рекурсивные и примитивно рекурсивные йшоже-ства. Подмножество А дшожества всех натуральных чисел N называется рекурсивным {прилттивно рекурсивным), если характеристическая функция множества А частично рекурсивна (соответственно примитивно рекурсивна).

Так как все нримитивпо рекурсивные функции частично рекурсивны, то каждое примитивно рекурсивное множество рекурсивно. Обратное неверно: в и. 5.2 будет построены рекурсивные множества, не являющиеся примитивно рекурсивными.

С точки зрения теории алгоритмов из двух введенных понятий - рекурсивного множества и примитивно рекурсивного множества - основным следует считать первое благодаря следующему обстоятельству.

Проблемой вхождения для числового множества А называется задача отыскания алгоритма, который по стандартной заппсп (например, десятичной) произвольного натурального числа а позволяет узнать, входпт число а в А п.чп нет, т. е. позволяет вычислять значения характеристической функции множества А. В силу тезиса Чёрча существование такого алгоритма равносильно рекурспв-иостп характерпстическоп функции. Поэтому можно сказать, что рекурсивные множества - это множества с алгоритмически разрешимой проблемой вхождения.

Выведем теперь несколько основных свойств рекурсивных и примитивно рекурсивных множеств.

Характеристическплгя функциями пустого множества 0 и множества всех натуральных чисел Ж являются постоян-