ГЛ. 1. ОСНОВНЫЕ понятия

Основное определение частичной рекурсивности дает: соЬокушость всех частичных функций, частично рекурсивных относительно заданной системы частичных функций ©, есть подалгебра алгебры 51, порожденная в S[ системой ©, 7", о, s.

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

S(i= <i; Ж, Д, S S=, . . .>

алгебры. S(. Совокупность всех общерекурсивных функций есть подалгебра алгебры иорожденная в 5(( простейшпыи функциями о, 1, S.

5. Доказать, что каждая всюду определенная функция, равная натуральному числу а. везде, за исключением конечного числа точек, является примитивно рекурсивной.

6. Доказать примитивщчо рекурсивность двуместных функций [х/у], rest {х, у), где [х/у] обозначает (неполное) частное, а rest {х, у)- остаток от деления х на у. По определенсшо полагаем также, что [х/0] = г и rest (х, 0) = х.

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

8. Показать, что примитивно рекурсивна каждая

а) конечная совокупность чисел;

б) совокупность чисел вида ага Ь (ге = О, 1, 2, . . . );

в) совокупность чисел вида а-Ь" (ге = О, 1, 2, . . .).

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

ГЛАВА П

ПРЙМИТВШНО РЕКУРСИВНЫЕ ФУНКЦИИ

И РЕКУРСИВНО ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА

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

§ 3. Примитивно рекурсивные функции

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

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

Теорем al. Пусть п-местная [частичная) функция g примитивно рекурсивна {относительно какой-нибудь системы частичных функций ©). Тогда п-местная Функция /, определенная равенством

/ (агь . .. , Хп) = S g {xi,. . ., Хп-ъ г),

ишкжг примитивно рекурсивна {относительно ©). Действительно, из указанного равенства вытекает

/ {Xi, . . ., Хп-1, 0) = g {Xi, . . ., Xn-l, 0),

/ (a-i, . . ., Хп-1, г/ -Ь 1) =

= / {xi, . . ., Хп-1, у) + g {xi, . . ., Хп-1, у -Ь 1).

гл. II. РЕКУРСИВНЫЕ ФУНКЦИЙ

Следовательно, функция / возникает посредством примитивной рекурсии из примитивно рекурсивных функций

g . . ., Xn-i, 0), h {xj,, . . ., Xn-i, У, z) =

z + g . . ., Xn-i, у + V и потому / примитивно рекурсивна.

Следствие 1. Если п-жстная всюду определенная функция g примитивно рекурсивна {относительно ©), то {п -f \)-местная функция /, определенная схемой

/ {хг,. .., Хп-ъ У, z) =

У g {xi,. .., Xn-i, i), если г/ < z, О, если yz,

также примитивно рекурсивна {относительно ©). Из схемы (1) видно, что

f{Xi,...,Xn-i,y, Z) =

= ( S (1. • • • > g {и • • • , n-l, I)) +

+ g{xi,.. .,Xn-i, y)-sg{yz).

Так как операция - примитивно рекурсивна, то в силу теоремы 1 функция / также примитивно рекурсивна.

Иногда говорят, что определенная в теореме 1 функция / возникает из функции g операцией суммирования. Теорема 1 означает, что операция суммирования, произведенная над примитивно рекурсивной функцией, дает снова примитивно рекурсивную функцию.

Следствие 2. Если g, h, к - примитивно рекурсивные,функции, то функция /*, определенная соотношением

f*{xi,...,Xn)= S g{xi,...,Xn-i,i), (2)

также примитивно рекурсивна.

Формула (2) равносильна формуле

/* {х, . . ., а;„) = / {xi, . . ., Xn-i, h, к),

где / - функция, определенная схемой (1). Так как f,h, к примитивно рекурсивны, то /* также примитивно рекурсивна.

Аналогично теореме 1 доказывается и

Теорема 2. Если п-жстная функция g примитивно рекурсивна {относительно системы функций @), то п-мест-ная функция, определенная формулой

f {xi,..., Xn-t, Хп) =Wg {хг,. .., Xn-i, i),

•) Xji)

такзюе примитивно рекурсивна {относительно ©).

В этом случае говорят, что функция / {х, . . получается из функции g (ж, . . ., х„) операцией мультиплицирования.

Доказательство ввиду его простоты мы опустим.

Далее часто будет встречаться так называемое кусочное задание функции. Заключается оно в следующем. Пусть заданы некоторые функции {xi, . . ., х„), i = 1, . . . . . ., S + 1, и указаны какие-то условия Pj {х., . . ., Хп) (/ = 1, . . ., s), которые для любой системы чисел х-, . . . . . ., Хп могут быть истинны или ложны. Допустим, далее, что ни для одной системы чисел х, . . ., Хп никакие два из упомянутых условий не могут быть одновременно истинными. Функция / {xi, . . ., Хп), заданная схемой

7i {xi,.. ., Хп), если Pi {xi,. .. , Хп) истинно,

/г {xi,. . ., Хп), если {xi,. . ., Хп) истинно.

f{Xi,.. .,Хп)=

/., {xi,..., Хп), если Ps {xi,..., Хп) истинно,

• /т {xi,. . ., Хп) для остальных xi,.. ., Хп,

называется функцией, определенной кусочной схемой. Будет ли функция / примитивно рекурсивной, зависит от природы функций /г И УСЛОВИЙ Pj. Простейший случай заведомо примитивно рекурсивной функции / даёт

Теорема 3. Пусть заданы п-местные примитивно рекурсивные {относительно @) всюду определенные функции Д, . . .,/s+i, а, . . ., а, причем ни при каких значениях переменных никакие две из функций а, . . ., одно-вре.ченно в О не обращаются. Тогда функция /, определенная кусочной схелюй

ifi {xi,Хп), если ai {xi, . .., а;„) = О,

f{Xi,...,Xn) =

/, {хх,. . ., Хп), если а, {xi,. . ., х„) = О, fsi{xi,. . ,Хп) в- остальных случаях, будет примитивно рекурсивной {относительно @).

Для доказательства достаточно заметить, что функцию / можно представить в виде

/ = /Isg ai + . . . -f Л sg а, + /s+isg («1 . . . а,),

где sg, sg - введенные в и. 2.2 примитивно рекурсивные одноместные функции.

В теореме 3 рассмотрен типичный случай, когда условия Pi имеют вид ttj- =0. Так как условия вида

= Рь ОС; < Рь ОС, < Р; (3)

равносильны соответственно условиям

I а, - Рг I = О, а, - р; = О, s (Р; - а,-) = О,

то теорема 3 останется справедливой и в том случае, когда в кусочной схеме равенства а, = О заменяются но произволу требованиями вида (3), где «ь Р; - примитивно рекурсивные функции.

Рассмотрим уравнение

g (ж!, . . ., ж„, г/) = О, (4)

левая часть которого есть всюду определенная функция. Допустим, что для каждых значений ж, . . ., ж„ уравнение (4) имеет единственное решение у. Тогда это решение будет однозначной всюду определенной функцией от ж, . . . . . ., ж„. Спрашивается, будет ли эта функция у = = f («1, . . ., ж„) примитивно рекурсивной, если левая часть уравнения (4) есть примитивно рекурсивная функция от Жх, . . ., ж„, у. В главе IV будет показано, что в обш;ем случае ответ на этот вопрос отрицателен. Это не исключает, конечно, возможности, что в отдельных случаях ответ будет положительным.

Теорема 4 (о манорнруедшх неявных функциях). Пусть g (жх, . . ., Хп, у), ос (ж, . . ., ж„) - тате примитивно рекурсивные функции, что уравнение

g (Ж1, . . ., Хп, у) = 0 (5)

для каждых ж, . . ., л;,, ижет по меньшей мере одно решение и

IX,,, {g (Ж1, . . ., Хп,. г/) = 0)< а (ж, . . ., х) (6) для любых Жх, . . ., ж„. Тогда функция

/ (Жх, . . ., ж„) = ц„ {g (Жх, . . ., Хп, у) = 0) также примитивно рекурсивна.

Вводя примитивно рекурсивную функцию

h (Ж1,. . . ,x„,z) = [[ g (xi,. .. ,Хп, i), мы сможем переписать равенство (8) в форме

.....ж„)

/(Ж1, ...,ж„)= 2 sgh{xi,. . . ,Xn,i).

В силу теорем 1, 2 отсюда следует, что функция / примитивно рекурсивна.

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

Начнем с частного и остатка от деления числа ж на число у, которые будем обозначать через [х/у] и rest (ж, у). Чтобы шють дело с всюду определеннымп функциями, дополнительно положим, что

[ж/О] = ж, rest (ж, 0) = ж

для всех X. Ясно, что так определенные функцпп связаны тождеством

rest (ж, г/) = ж- [уШу])

Фиксируем какие-нибудь значения ж., . . ., ж„ и пусть а = t!/ (1 • • •. п, у) = 0). Рассмотрим последовательность произведений

g (Жх, . . ., Хп, 0) g (Ж1, . . ., Хп, 1) . . . g (Ж1, . . ., х„, i)

{i = О, 1, 2, . . .). (7)

Так как у = а есть наименьшее решение уравнения (5), то первые а членов последовательности (7) нулю не равны, а все остальные члены содержат равный нулю сомнояи-тель g (xi, . . ., Хп, а) и потому равны нулю. Поэтому из условия (6) вытекает, что

а= S sgig{xi,...,Xn,0)...g{xi,...,Xn,i)).