и потому функция о" примитивно рекурсивна. ПроизволЬ-» пая п-местная постоянная функция/" = а допускает представление в виде терма

..в(о"(а;ь .. . , . ..)),

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

Двуместная функция f {х, у) = х у удовлетворяет соотношениям

x-\-Q = х = 1\ {х), x + {y + i) = {x + y) + \=s{x + y).

Следовательно, функция х у возникает из примитивно рекурсивных функций !{, h {х, у, z) = z + I операцией примитивной рекурсии и потому функция X -\- у примитивно рекурсивна.

Двуместная функция ху удовлетворяет схеме примитивной рекурсии

X-Q = о {х), х{у + i) = ху + X

с начальными примитивно рекурсивными функциями (см. (1), (2))

g{x) = о (ж), h {х, y,z) = Z + X.

Поэтому функция ху примитивно рекурсивна.

Рассмотрим функцию х", причем будем считать, что ж" = 1. Соотношения

ж" = 1,

= хх

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

g (х) = 1, h (х, у, z) = Z-X.

Поэтому функция ж- также примитивно рекурсивна.

В-нализе иногда встречается функция sg х {сигнум-аяя знак х), равная -fl для положительных вещественных значений символа х, -1 для отрицательных ж и О для ж = 0. Мы будем рассматривать эту функцию лишь для натуральных значений х, для которых она может быть

sgж =

sgж =

определена так:

0, если ж = 0,

1, если ж>0. Введем еще функцию sg, определяемую так:

1, если ж = 0, О, если ж>0,

н совпадающую c j)a3H0CTbro i - sg х.

Функции sg и sg удовлетворяют примитивно рекурсивным схемам:

sgO = 0, sgO = l, sg (ж + 1) = 1, sg (ж -Ы) = 0 имеющим вид (3), (4). Поэтому функции sg и sg примитивно рекурсивны.

В области натуральных чисел разность х - у естественно считать частичной двуместной функцией от ж, у, определенной лишь для ж > z/, так как отрицательные числа не входят в рассматриваемую область. Но примитивно рекурсивные функции всюду определены. Поэтому в теории примитивно рекурсивных функций вместо обычной разности вводят усеченную разность, обозначаемую символом - и определяемую так:

х - у, если ж>1/,

[ О, если ж<г/.

В отличие от простой разности- усеченная разность является всюду определенной в области натуральных чисел, и в то же время она очень просто связана с обычной разностью. Так, например, согласно (6)

5 3 = 2, 3 5 = О, (ж I/) Z = ж (I/ + Z).

Функция ж - 1 удовлетворяет прилштивно рекурсивной схеме

01=0, (ж -Ь 1) 1 = ж с примитивно рекурсивными начальными функциями и Г1. Поэтому функция ж 1 примитивно рекурсивна. С другой стороны, из (6) следует, что для любых ж, у

ж - О = ж, x-{y + l) = (x-y)i.

Эти тонодества показывают, что двуместная функция X - у возникает примитивной рекурсией из функций 1\ и h [х, у, z) = Z - i. Обе последние функции примитивно рекурсивны. Поэтому и функция х--у примитивно рекурсивна.

Наконец, из примитивной рекурсивностп функций + и - вытекает примитивная рекурсивность функции

\ X - у \ = (х у) + {у х).

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

В настоящем и предыдущем пунктах на множестве Э всех частичных функций с произвольным числом аргументов были определены частичные операции суперпозиции S (г = 2, 3, . . .) и примитивной рекурсии JR,. Согласно п. 1.3 система

является частичной алгеброй. Из приведенных выше определений неносредственно вытекает, что совокупность gnp всех примитивно рекурсивных функций является подалгеброй алгебры S5, порожденной системой функций о, Im (та, тг = 1, 2, . . .). Аналогично, если @ - система каких-либо функций из то совокупность всех функций, примитивно рекурсивных относительно ©, является подалгеброй алгебры SB, норожденной функциями системы © и простейшими функциями о, s, Im- В си.лу теоремы 1 из п. 1.3 можно утверждать, что примитивно рекурсивными являются те и только те функции, которые являются значениями термов, записываемых с помощью индивидуальных предметных символов о, s, Im и функциональных символов R, 8, 8, . . .

Аналогично, те и только те функции примитивно рекурсивны относительно ©, которые являются значенияьш термов, записываемых с помощью индивидуальных предметных символов о, S, 1т, СИМВОЛОВ функций ИЗ © И функциональных символов JJ, 8, 8, . . .

Тердш этих ВИДОВ мы, как и в п. 2.1, будем называть операторным. С формальной точки зрения операторные термы - это слова в алфавите, образованном символами В, 8"-, о, S, Im И символам, которые обозначают функции

из системы @. Как правило, система © предполагается конечной, но даже и в этом случае алфавит получается бесконечным, так как он включает бесконечное число символов 8, 8, . . . Однако эту сложность легко устранить, если воспользоваться надлежащим кодированием, указанным, например, в и. 1.4. Тогда каждая примитивно рекурсивная функция будет значением подходящего слова в фиксированном конечном алфавите.

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

х-1=В{о,11)(х),

=В{1\, П1) = В{!{, 8 (В {о, 1\), П)).

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

2.3. Операция минимизации. Рассмотрим какую-нибудь /г-местную (тг > 1) частичную числовую функцию /. Допустим, что существует какой-либо «механизм» для вычисления значений функции /, причем значение функции / не определено тогда и только тогда, когда этот механизм работает бесконечно, не выдавая никакого определенного результата. Фиксируем какие-нибудь значения х-, . . ., Хп-1 ДЛЯ первых тг - 1 aj)ryMeHTOB функции / и рассмотрим уравнение

/ {Хх, . . ., Х,г-1, у) = Х,г.

Чтобы найти решение у (натуральное) этого уравнения, будем вычислять при помощи указанного выше «механизма» последовательно значения / {х, . . ., х,,-!, у) для у = = О, 1, 2, . . . Наименьшее значение а, для которого получится

/ (xj , . . ., Хп-1, а) = Хц,

через

liy (/ (жх, . . ., хп-и у) = Хп). (2)

Описанный процесс нахождения значения выражения (2) будет продолжаться бесконечно в следующих случаях:

а) значение / (ж, . . ., ж„ 1, 0) не определено;

б) значения / (ж, . . ., Xn-i, г/) для у = 0, 1,..., а - i определены, но отличны от ж„, а значение / (ж1, . . . . . ., Хп-1, а) не определено;

в) значения / (ж, . . ., Жп-i, у) определены для всех г/ = О, 1, 2, . . . и отличны от ж„.

Во всех этих случаях значение выран<ения (2) считается неопределенным. В остальных случаях описанный процесс обрывается и дает наименьшее решение у = а уравнения (1). Это решение, как сказано, и будет значением выражения (2).

Например, мы уже условились обозначать через х - у. функцию, равную обычной разности х - у для ж > г/ и нулю для X <iy. Поэтому в согласии с указанным смыслом символа \i для всех ж, у имеем

ж - I/ = (хЛу + Z = ж).

Аналогично,

(зёЖ = 1) = 1,

[А?/ (г/ ж = 0) = 0.

Это соответственно наименьшие решения уравнений sg ж = = 1 и г/ - ж = 0.

Напротив, значение выражения

Vy (У {у-{х + 1)) = О (4)

не определено, так как уже значение терма О-(О - ( ж -f-+ 1)) не определено. В то же время уравнение

(у-(ж + 1)) = 0

имеет решение у = х + i, so оно не совпадает с значением выражения (4). Этот пример показывает, что для частичных функций/ (ж1, . . ., Хп-х, у) выражение (2), строго говоря, не есть наименьшее решение уравнения (1). Если же функция / (жх, . . ., ж„ 1, у) всюду определена и уравнение (1) имеет решения, то (2) есть наименьшее решение для (1).

Значение выражения (2) при заданной функции / за-рисит от выбора значений для параметров Xi, . . ж-,

Хп И потому оно есть функция (частичная) от аргументов Xi, . . Хп- Эту функцию мы будем обозначать символически через Mf, где М - символ операции, переводящей функцию / в функцию Mf. Если заданная функция / одноместна, то функцию Mf обозначают часто через / и называют обращением функции / или, короче, обратной функцией. Таким образом,

Г (х) = fi„ (/ {у) = ж).

Например, для функций sg ms обратными будут функ-

sg 1ж

= ж, если ж = 0,1,

не определено, если ж>1,

и соответственно

s- (ж)

--Х - 1 если ж О,

не определено, если ж -0.

Для многоместных функций / запись /~ не употребительна. В дальнейшем оператор М будет называться оператором минимизации. Например, из формулы (3) получается

м (+) = /»«(-, П, П).

Наряду с выражениями вида (2) далее нам будут встречаться выражения вида

fly (/ (Ж1, . . ., ж„, у) = g (Ж1, . . .,Хп, у)),

\1у (/ (Ж1, . . ., ж„, у)ф g (Ж1, . . ., Хп,у)).

Значения их считаются по определению совпадающим с значениями соответственно выражений

V-V (1/ {хх, . . .,хп,у) - g (Жх, . . ., Хп,у) I = 0),

(sg I / (Жх, . . .,Хп,у) - g (Жх, . . ., ж„, у) I = 1).

Теперь введем следующее

Основное определение. Частичная функция / называется частично рекурсивной относительно системы частичными функций @, если / может быть получена из функций системы © и простейших функций о, Im конечнът числом операций подстановки, примитивной рекурсии и минимизации.

обозначим