функции h [у, z) рекурсией

/ (0) = о, / (Z/ + 1) = /г {у, f (у)),

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

Ф (0) = О, Ф (г/ + 1) = Ф (ф Ы),

где Ф - подходящая суперпозиция функций h, с, 1,г,

о, S, 1т.

Теорема 2. Частичная функция f (ж, . . ., Хп), получающаяся из частичной функции g (xi, . . Хп, у) операцией минимизации

f [хх, . . ., Хп) = (g (xi, . . ., Хп, у) = 0), (8)

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

F (х) = liy (G {X, у) = 0). (9)

Действительно, вводя фзшкцию

F {х) =f (c„i (х), . . .,Спп (х)),

получим

f{Xi, . . Хп) F {С {Хи . . .,Хп)).

в то же время из (8) вытекает

F (х) = {G {х, у) = 0),

G {х, у) = g (c„i {х), . . ., Спп {х), у), .

Из теорем 1 и 2 непосредственно получаем Следствие. Каждая функция, частично рекурсивная относительно системы частичных функций <В, может быть получена из функций системы © и функций с,1, г, о, S, 1т конечным числом операций подстановки, специальных рекурсий вида (2) и специальных минимизаций вида (9).

Столь же просто доказывается и"

"Теорел1аЗ (Гёдель [1]). Функция ф {х, . . . . . Хп, у), получающаяся примитивной рекурсией (1) из всюду определенных функций g {х, . . ., Хп) h (xi, . . . . . ., Хп, у, z), может быть получена из этих функций и функций Г, с, I, ), 4", -, S, о, If конечным числом подстановок и минимизаций,

Ввиду теоремы 1 достаточно провести доказательство лишь для случая, когда д = 1 и рекурсия имеет специальный вид (2). Полагая х, у произвольно заданными числами, рассмотрим систему уравнений относительно z:

Г (z, 0) = ср {х, 0), Г (2, 1) = ф {х, 1), . . ., Г (z, у) .=

= ф {х, у), (10)

где Г (z, у) - функция Гёделя из п. 3.3. В силу (2) эту систему дгояшо переписать в виде

Г (Z, 0) = х, Г (Z, U -Ы) = Ф (Г (z, и)) (О < к < г/) или

П,0) = .,

u(j/- u\rg\r{z, u + i)-O{T{z,u))\ = 0)=y. -

Множитель [ у ~ и \ введен здесь для того, чтобы функция

F {у, Z) = (х„ {1у-и\ sg I Г (Z, м + 1) - Ф(Г(2, и))\ =0)

была всюду определенной. Согласно основному свойству функции Г система (10), а значит, и равносильные ей система (11) и уравнение

T{z,0)-x\-\- \ F{y,z)-y\ = 0

(12)

имеют решение z для каждых х, у. Так как левая часть уравнения (12) является всюду определенной функцией, то формула

Z = [1и {\ {и, 0) - X \ + \ F {у, и) - у \ 0)

дает наименьшее решение z системы (10). Обозначая это решение через G {х, у), из последнего уравнения системы (10) получим

Ф {х, y)=T(G {х, у), у).

Такп.л1 образом, функции F, G п (р получаются подстановками и минимизациями из функции Ф и функций Г, -Ь, -, /Г. Дополнительные фзгнкции с, I, г, s, о указаны в теореме 3 для того, чтобы можно было применить теорему 1 и свести дело к случаю рекурсии специального вида (2). С другой стороны, с их помощью легко получаются

использованные функции х-у и sg х. Именно,

sgx=i -х = so {х) - х -so {х) -1\ {х), M = t,(i/--(22-fl) = 0), с (ж, ж) = 2ж2 + 2ж, 2ж= = с (ж, ж) - 2ж, ж = [2ж2/2],

X - у - \ J .

Согласно и. 2.4 функция называется общерекурсив-ной, если она может быть получена из простейших функций операциями подстановки, примитивной рекурсии и операциями минимизации, не выводящими за пределы всюду определенных функций. Поэтому из теоремы 3 следует, что каждая общерекурсивная функция может быть получена из функций Т, с, I, г, s, о, +, -, IT конечным числом подстановок и специальных операций минимизации вида (9), применяемых лишь к таким функциям, для которых результатом минимизации служит всюду определенная функция.

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

3.5. Одноместные примитивно рекурсивные функции. Указанное в п. 2.2 основное определение примитивно рекурсивных функций имеет смысл лишь тогда, когда рассматриваются одновременно функции от любого числа аргументов. Однако довольно часто встречается положение, когда достаточно рассматривать лишь функции одной переменной. Поэтому естественно возникает вопрос: нельзя ли найти такое определение понятия примитивной рекурсивности одноместных функций, которое выражалось бы целиком в терминах теории одноместных функций? Доказываемая ниже теорема Р. Робинсона дает положительный ответ на этот вопрос. Получается она надлежащим усилением теоремы 1 пз предыдущего раздела.

Рассмотрим следующие операции над одноместными частичными функциями:

а) Двуместная операция сложения одноместных частичных функций. Эта операция обозначается символом -- и определяется формулой

(/ + g) {х) =f{x) + g (ж).

б) Двуместная операция композиции одноместных частичных функций.

Эта операция обозначается далее символом * и определяется соотношением

{f*g){x)=f{g{x)).

в) Одноместная операция итерирования одноместной частичной функции. Эта операция далее обозначается символом J и определяется следующим образом: говорят, что одноместная частичная функция / возникает операцией итерирования из одноместной частичной функции g (символически / = = Jg g"), если

/(0)=0, /(/г + 1) = (/(д)).

Конечно, операции J легко выразить через

прежние операции. Например, ясно, что

/ + g = /, Я), fg = S (/, g),

Jg=B (о, 8 (g, П)).

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

Теорема (Р. Робинсон [1]). Все одноместные примитивно рекурсивные функции и только они могут быть получены из функций s {х) = х -\- i и g (ж) = ж - [ YxY конечным числом операций сложения, композиции и итерирования функций.

Условимся временно называть одноместную функцию / допустимой, если она может быть получена из функций s и q конечным числом операций -f, *, J. Нам надо доказать два утверждения:

1) все допустимые одноместные функции примитивно рекурсивны;

2) все примитивно рекурсивные одноместные функции допустимы.

Первое утверждение очевидно, так как исходные функции S ъ q примитивно рекурсивны, а операции сложения, К01Ш03ИЦИИ и итерирования, примененные к приьштивно рекурсивным функциям, дают снова примитивно рекурсивные функции. Поэтому дело сводится к доказательству второго утверждения.

Прежде всего распространим понятие допустимости и на многоместные функции, называя ге-местную функцию / (жх, . . ., Хп) (л > 2) допустимой, если для любых од-

ГЛ. It. РЕКУРСИВНЫЕ ФУНКЦИИ

поместных допустимых функций ai (), . . ., а„ {t) одно- 1 местная функция / (а (it), . . ., {t)) является допустимой. А теперь вместо утверждения 2) будем доказывать более обш;ее утверждение:

3) все (одноместные и многоместные) примитивно рекурсивные функции допустимы.

Доказательство разобьем ни ряд вспомогательных утверждений, из сопоставления которых и нолуяится утверждение 3).

А) Суперпозиция и сумма допустимых функций (с любым числом аргументов) суть функции допустимые. В самом деле, пусть g {х, . . ., а;„), {х, . . .

• , Хт), . . .,К (Xi, . ., Хт) допустимы И / {Xi, . . .,Хт) = g (hx [Хх, . . .,Хт), . . ., К [Хх, . . ., Хт)).

Тогда для любых допустимых функций (i), . . . . . ., (i) одноместная функция

/ («1 {t), . . ., (0) = g (Pi {t), . . ., Р„ (0),

{t) =hi (ai(i), . . ., a[t)) (J = 1, . . ., и),

будет допустимой, так как по условию функции g, Л; допустимы. Но тогда допустима и функция /. Аналогично доказывается и допустимость суммы допустимых функций.

Б) Одноместные функции о, l\, sg, sg и многоместные

функции 1т, ах -{- by с, где а, Ъ, с - фиксированные натуральные числа, являются допустимыми.

Допустимость функций ll, о, sg,. sg вытекает из очевидных соотношений

= = sg = (s*o) a; = «7(2-L2sga;).

Так как для допустимых функций «1 (i), . . ., а„ (t) функция

Гт («1 it), . . ., а„ (0) = СХт (t)

допустима, то Гт допустима. Наконец, из формулы

ax-\-by + c = rUx,y) + ...+lt (х, у).-\- ... -Ь 14-

+ . . . +1

и допустимости суммы заключаем, что функция ах -\--\- by -\- с также допустима.

§ 3. ПРИМИТИВНО PEKyPGHBIiblE ФУНКЦИИ 71

В) функция х допустима. Б силу Б) функция [1, если х - полный квадрат,

[V, если х - неполный квадрат, допустима. С другой стороны, равенства 0 = О и (ж -Ь 1) = а: + 22: + 1 = ф (х) + I,

(pit) = t + 2 [ft], показывают, что есть итерация функции ф -)- 1. В свою очередь, равенства ф (0) = О и

Ф -f 1) = Ф (i) 4- 1 + 2 ([fT+l] - iVt]) =

= Ф (i) -Ь 1 + 2 sg 3 (Ф (О 4- 4)

показывают, что ф получается итерированием функции

а() (li) = ц 4- 1 4- 2 sg g (м 4- 4). Так как последняя функция допустима, то допустимы функции ф и ж.

Г) Функции [х/2], [Yx], ху, X - у допустимы. Из А), Б), В) следует, что функция q {{х 4- у) -j- 5х Зу -\- i) допустима. Так как

(х + у) -\- 5х + Зу + i = {х + у -\- 2) -\г X - у,

то для х у имеем (ж 4- 4-2)= < (о: 4- У 4- 2)2 4- - г/ < (о; 4- У 4- 3)2

и, следовательно,

q {{х + у)- + Ъх + Зу + ) = X - у {х у).

Если же X <у, то из {x + y + i)<{x + y-\-i) + dx + y + 3==

= (ж 4- г/ 4- 2)2 4- л; - г/ < (ж 4- У 4- 2)2

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

Q{{x + y) + 5x-h3y + i) = 3x-hy-h{x< у).

Вводя для q {{х 4- у) -\- 5х -\- Зу -j- 4) обозначение х ~ Уг приходим к заключению, что функция X у,