4) Итерация В-маокорируемой функции В-мажорируема. Пусть для X 2 имеем f {х) <С В (д, х). Положим

т= п+f{0) + f{i) + f{f (0)).

Итерация g (х) функции / (х) определяется равенствамп

g{0) = 0, g{x+i) = f (g (х)).

Покажем, что

g{x)<B (т, X) {X > 2). (8)

Для X = 2 имеем g{2) = f (/ (0)) < 2«"»>+1 < В (ге, / (/, 0)) + 1) < В [т, 2).

Далее, по индукции предположим, что для некоторого 2 неравенство (8) справедливо. Рассмотрим g {х -\- 1). Возможны два случая: а) g (х) % 2 и ) g (х) = О, i. В случае а) имеем

g{x+i)=fig (х)) <В (х, g (х)) < В (,« - 1, В (т, X)) =

= В (то, х-\- 1).

В сл5чае Р) снова имеем

g (а; + 1) = / (g (:,)) < / (0) -f / (1) < 2"-" <

< в (re, m - re -Ь г -f 1) < В (;ге, х + 1).

Таким образом, утверждение 4) доказано.

Теперь для вывода леммы остается лпшь сослаться на теорему Р. Робинсона из п. 3.5. Согласно этой теореме все примитивно рекурсивные функции получаются из функций s (х) и q {х) сложениями, суперпозициями и итерациями. Но согласно!) функции s, q В-мажорируемы. Согласно 2) - 4) операции сложения, суперпозиции и итерации, будучи применены к В-мажорируемым функциям, дают снова В-мажорируемые функции. Поэтому все одноместные примитивно рекурсивные функции В-мажорпруемы.

Докажем, наконец, теорему 1. Пусть / (х) - некоторая примитивно рекурсивная функция. Согласно лемме для подходящего ге при всех а; > 2 будем иметь f (х) < В (ге, х). Но тогда

А (п+ х) = В {п + X, п -{- .т) > В (ге, п + х) > f [п + х) (х>2),

что и требовалось.

. 5.4. Обращение функций. .Ллгебра Робинсон. Согласно основному определению (п. 2.4) всюду определенная одноместная функция / (х) называется общерекурсивной, если ее можно получить пз базисных фтакций S {х) = X -г i, о, 1 с помощью конечного числа операций подстановок, примитивных рекфсий и и-операцпй. Таким образом, для решения вопроса о рекурсивности одноместной функции / [х) мы должны строить / {х) из многоместных функцпп. Естественно вознпкает вопрос, а нельзя ли указать такие операции и такие одноместные исходные функции, чтобы все одноместные общерекурсивные функпип и только пх можно было полу-ч]!ть из исходных, оставаясь все время в классе одно.местных функций? Аналогичный вопрос уже ставплся п был решен в и, 3,5

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

Пусть / (х) - произвольная одноместная частичная функция. Согласно п. 2.3 функция g (х), определенная формулой

g(x) = liy (f(y) = х),

называется обратной для / {х) и обозначается символически через

Оператор, ставящий в соответствие функции / функцию /"i, пазывается оператором обращения. Легко видеть, что обратная функция f~ {х) будет всюду определенной тогда и только тогда, когда заданная функция / {х) всюду определена и совокупность ее значений совпадает со всем натуральным рядом.

Основпой пашей целью сейчас является доказательство следую-п1,сго результата.

Теорема 1 (Ю. Р о б и н с о и [1]). Каокдая общерекурсив-пая одно.кестпая функция мажет быть получена из функций S {х) = = X -\- i и q {х) X - конечным числом операций сложения,

суперпозиции и обращения одноместных функций. При этом операция обращения выполняется только тогда, когд(1 результатом ее является всюду определенная функция.

Доказательство этой теоремы в целом аналогично доказательству соответствующей теоремы Р. Робинсона о приьштпвно рекурсивных функциях из п. 3.5. Так же, как и в п. 3.5, одноместную функцию / [х) назовем допустимой, если она может быть получена из функций S, О" так, как указано в теореме 1. Многоместную функцию F [ху, . . ., Хп) мы будем называть допустимой, если для любых одноместных допустимых функций /i (х), . . ., fn (х) будет допустимой одноместная функция F (/, (х), . . ., fn (х)).

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

A) Суперпозиция {многоместных) допуспи.иых функций есть допустимая функция. Доказательство очевидно.

B) Функция q~ (х) всюду определена и

q- {2х) = .гз -Ь 2х, q- {2х -Ь 1) = х"- + ix + 2. (1) В самом деле, для любого х

< лг= + 2х <{х+ \Г- < л: + 4,г + 2 < (л: + 2)"-

II. значит,

q [х- + 2.Г:) = 2х, q {х + 4.r + 2) = 2л: -f 1. Таким образом, числа

г/ = г/о = .т= -L 2х, г = Jo = .г- -f 4а: -f 2

являются решенпЯ1Ш уравнений

q{y) = 2x, q{z)=2xi. (2)

Надо показать, что г/о, - наименьшие решения. Пусть y,z - какие-нибудь решения уравнений (2). Это значит, что

у = т- -1- 2а; < (т -Ь 1), z = ге -- 2а: -{- 1 < (ге -)- 1)2,

X у = q{{x + у-} + Ъх + Ъу -t-i) =

(3).

/ {у) -Ь 2q (у) = X.

Полагая j/j = (х -\- 1х/2У, -\- [х/2] и принимая во внимание соотношение / (г=) = / (г), nonjHM q (д) = [а:/2], / (у) = / (а;) и, значит,

2? (г/о) -Ь / (г/о) =2 [а;/2] -f / (а:) = х.

Это показывает, что уравнение (5) п.мсст решение для каждого а;. Поэтому функции {2q -{- f)- всюду определена, и, следовательно,

допустима. Из (5) вытекает, что

q{y)=jixfiy))

TiH любого у, удовлетворяющего соотношению (5). В частности, (lil должно быть верным и для у = {2q -Н /Г {х), то есть

д т + /)- {х)) =\{xt ix)) =

Следовательно, функция [а:,/2] допустима. Из очевидного соотношения

({X + у7 xXjt

ху -

заключаем, что допустима и функция ху. Из формулы (3) вытекает, что

Цху) + У)х= °

а;>г/>

2х-2у + 2,, х<у.

Поэтому, вводя функцию

.(а:,г/)=з1((а:г/) + г/-)=и;

иудем иметь

ху = v{x, у) (х -h !/).

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

ш (а;) =

• £2 X.

Для а: = О пмеем w (0) = 0. Если же х= t,f>0, то

ш(г2) =

!?((«-1, + 2*-2)

+ i={2t-2) + i = t.

С.чедовательно, для любого t пмеем w (fi) = t п потому w{xq ix)) = w ([i/.7P) = []/x]

Л.1Я каждого X. Формулы (7), (8) показывают, что функция/х] .1 шустпма.

Е) Канторовские функции (п. 3.3) с (х, у), I {х), г (.г) допустимы.

Эти функции получаются из функции 1, х, у с помощью операций -{ [j/"] [/2], которые согласно доказанному не выводят за пределы класса допустимых функций.

Ж) Если функция h (х, у) допустима и уравнение h (а:, г/) = О разрешимо д.гя каждого х, та функция

f (х) = Ну (Л ix, у) = 0) (9)

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

Положпм г = с (а;, у). Тогда х = I (z), у =г (г). Так как канторовский помер Z = с (х, у) пары <.т, у> при фиксированном х

Отсюда следует, что х<т, х -\- 1и потому у=т+2х:+2х = у„ Z = ге! -Ь 2а: -Ь 1 -Ь 1)2 -t- 2а; -Ь 1 = 2о.

Таким образом, формулы (1) истинны.

В) Функции X, о, X -\г у, II {ху, . . ., Хп) = Xi допустимы. Это непосредственно вытекает из очевидных формул

q (0-1 (х)) = X, q {5--! (а: + а:) + 1) = о

и определенпя допустимости функций.

Г) Функции вида ах -\- by -\- с, где а, Ь, с - произвольные фиксированные натура.гьные числа, допустимы.

В силу А), В) функции l\ (.г, у) = х, 1% {х, у) = у, s (0) = 1 допустимы, функция ах -\- Ьу -\- с возникает из упомянутых функций повторными сложениями и потому сама допустима.

Д) Функции а:2, sg а:, Sg а;, [а:/2], ху, х - у, [fx] допустимы.

В п. 3.5 была введена функция

х-у, ху,

[Ъх + уЪ, х<у.

В силу Б)

{X + yf- Jr 5.Г + 3i- -h 4 = y-i (2a: + 2z,) + 3a: + j/ -f 4

и потому на основании Г) функция х ч- у допустима. Теперь из очевидных формул

х = q~ (2а;) н- 2а:, sg а; = (а: -- 1), sg а; = 1 -f- sg а;

заключаем, что функции х, sg х, sg х допусти&ш. Сложнее вывести допустимость [а;/2]. Пусть

/{х) = Щ (q {q- {х) + 2)). Для а: = 2i согласно Б) имеем

/ (а:) = ii" {q {Р + 2t + 2)) - 0. Если же а; = 2г -г 1, то

fix) = ig(Q (/2-Ь 4/-Ь 4)) = 1.

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

является строго растущей функцией аргумента у, то справедливо равенство

/ () = Ми {h {х, ;/) = 0) =

= г (р, [I [z) = x&h(l (2), г (z)) = о». (10)

Введем функцию g определением

g{z)= liz).h{l(z), r{z)). (И)

Для а; > О из равенства g (г) х следует х = I (z) и h (х, г (z)) = 0. Отсюда

rg 1 (х) =

(12)

О, если х = 0, .f{x), если а;>0.

Таким образом, функция ?-g~- совпадает с / всюду, кронгс, возможно, а; = 0.

Из (12) получаем представление

/(а;) =/(O).sg (а:) + rg- {х).

(13)

Так как функции h, I, г, sg, +, допустимы, а / (0) - фиксированное число, то в силу (И) функции g и допустимы, а ввиду (13) допустима и функция /.

3) Функция [х/у] и функция Гёделя Г (а;, у) (и. 3.3) допустимы.

Это неносредственно вытекает из предыдущих результатов в силу формул из пп. 3.2 и 3.3, посредством которых определяются [х/у] н Г {х, у).

Доказательство теоремы Робинсон на этом можно считать законченным. Действительио, в п. 3.4 было доказано, что каждую обще-рекурсивную функцию можно получить из простейших функцпп О и функций -1", -, Г, е, I, г конечным числом операций под-

становки и специальной ьшнимизации вида (9). Но утверждения Д), Е), 3) показывают, что все упомянутые функции допустимы, а утверждения А), Ж) показывают, что подстановки и специальные ьшнимпзацип, примененные к допустимым функциям, дают допустимые функции. Таким образом, все общерекурспвные функцпп допустимы.

Аналогично теореме Р. Робинсона (и. 3.5) теорема Робинсон также допускает простое алгебрапческое истолкование. Совокупность всех всюду определенных и совокупность всех общере-кфсивны.\ одноместных функций, рассматриваемых" вместе с определенными иа них операцпялш сложения -г, композиции * и обращения -1, образуют две алгебры: алгебру Робинсон

%= <]; +, *,-Ъ всех одноместных функций п алгебру Робинсон

всех одноместных общерекурспвных функцпп. Операция прп-мененная к всюду определенной ф-инцпи, дает, вообще говоря, частичную функцию, не входящ5Ло в gJ. Поэтому алгебры ?Ri и 9?g г частичные. Теорема Робинсон утверждает, что элементы s, q в алгебре порождают подалгебру .

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

1. Пусть D (/г, х) - универсальная функция, построенная в 5 i. Если f (х) = D {п, х), то ге называется D-номером f {х). Показать, что каждая придпгтивно рекурсивная функция имеет бесконечно много Ю-номеров.

2. Показать, что существуют примитивно рекурсивные функции /(«, S (т, «), Л (ге), удовлетворяющие тояч-дествам

D (т, х) + D (ге, х) = D (j (;ге, ге), .г),

D {т, D (ге, а:)) = D {g (m, re), х),

D- [п, х) = D (h (re), x),

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

3. Функции, которые можно полушть из простейших функции о, S, операциями подстановки, примитивной рекурсии и рекурсии 2-ii ступени, назовем функциями 2-й ступени. Пользуясь методом быстрорастущих функций, показать, что существуют общерекур-сиппые функции, не являющиеся функциями 2-й ступени (см. П е-т е р [1]).

5. Пусть gJ г - совокупность всех одноместных частично рекурсивных функций. Операция обращения будет всюду оиреде-.чсииой иа gp J.. Показать, что элементы s, q являются порождающими алгебры <gp J.; +, *, ~Ь (см. п. 5.4).

•". Показать, что алгебра <gg г! *, порождается двумя под-.\(1ДИ1цими элементами и пе порождается никаким одним элементом. уикции с {г1 [х], 1г [х)), с [х, 1), с {I {х) -{- 1г (.г-), х) заведомо К)р(1ждают указаиную алгебру (Ю. Робинсон [1]).

0. Пусть 5" - совокупность всех двуместных частичных функ-ци11, 5-5, - совокупность всех двшстных частичных функций, частично рекурсивных относптельно какой-то фиксированной спсте-п.I © частичных функций. Показать, что порождается с помощью пюрацпп-}-, *, системой © и функциями1\, s (Z.), q {1% (Л/- "иорация мпнпьшзацпи, определенная вн. 2.3, операция * для двуместных фунжцпй определена в задаче 7 к § 3).

7. Верно, ли следующее утверждение: в алгебре <%, +, *, Ъ, I ,те 51 совокупность всех одноместных частичных функцпп, и11оизвольная система © С содержащая функции s, q, иорож-:iaoT подалгебру, состоящую из всех одноместных частичных функ-umi. частично рекурсивных относительно ©*)?

8. Показ;ать, что совокупность всех одноместных функцпп 2-й (тупенп (см. выше задачу 3) обладает общерекурспвной универсальной функцией (см. Петер [1]).

*) Ответ отрицательный; см. Поляков Е. А. Рекурсивные функции.- Иваново, 1978, с. 61-71.