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

Следствие. Для того чтобы операция F . . I . . ., Хт), определенная на Ж", была частично рекурсив ной, общерекурсивной или примитивно рекурсивной, н обходимо и достаточно, чтобы таковыми были все коорд натные функции (4) операции F.

Например, рассматривая целые комплексные числ Xi 1x2 как пары натуральных чисел {Xi, х}, видим, чъ операция сложения этих чисел является примитивно ре курсивной.

Аналогично, пусть заданы какие-либо примитивно р курсивные функции

g {хх, х, г/1, г/а), hi {х, х, уг, у) {i = 1, 2, 3, 4). Тогда двучленная операция F (f, t)), определенная на условиями

</ii {xi, . .., yi), hi {xi, .. . , г/2)>, если g{xi,..., г/2) = 0, </гз {xi, . . . , г/з), hi {xi,. . . , y)} i для остальных xi,. .., г/2,

.2>,<г/1,г/2» =

будет примитивно рекурсивной.

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

/1 (xi, Xi, уи г/з) =

/а (xi, Xi, Ух, yi) =

hi [xi, Xi, Уи yi),

если g(xi,. . .,yi) = 0, hs {xi, Xi, г/1, г/з) для остальных xi,... , yi,

hi (xi, Xi, Ух, yi),

если g{xi,Xi,yx,yi) = , hi {xx, Xi, г/1, г/з) для остальных х\, Xi, ух, у-2.

показывающими (см. п. 3.1), что эти координатные функции, а вместе с ними и операция F, являются приьштив-но рекурсивными.

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

Те о р е м а 4. Пусть на множестве Ж" всех п-ок натуральных чисел задано конечное число примитивно рекурсивных операций Fi (ji, . . ., 5„.) (i = 1, . . ., s) и пусть задано некоторое рекурсивно перечислимое множество V п-ок из Тогда совокупность п-ок, порожденная элементами V с помощью операций Fi, также рекурсивно перечислима.

Пусть с (F), с (F) - совокупности канторовских номеров ;7-ок из F и соответственно из F. Обозначим через /, (,Г1, . . ., Хт функцию, представляющую операцию Fi [ll, , ¥raj) (j = 1, • • •. s). Остается лишь убедиться, что множество чисел с (F°) порождается множеством с (F) с помощью операций Д, . . ., f, так как тогда ввиду теоремы 1 из п. 4.3 с (F) и F будут рекурсивно иеречисли-мыми.

Множество F есть совокупность значений термов, записываемых при помощи символов операций Fi и обозначений п-ок из V. Пусть а (fi, . . ., 5п) - один из таких термов. Заменяя в нем символы операцийсимволами представляющих функций fi, а символы ?г-ок символами их номеров, получим терм, значение которого будет равно номеру значения терма й. Таким образом, совокупность с (F) является дшожеством значений термов, записы-ваелшх при помощи символов функций fi и символов чисел пз с (F), т. е. с (F) порождается совокупностью с (F) при помощи функций fi, что и требовалось.

Согласно п. 1.3 множество М, снабженное конечной системой определенных на нем операций Fi {xi, . . ., Xmi), называется алгеброй, символически обозначаемой через

= <М;/?1, . . .,,>.

Если основное множество М алгебры 53? является совокупностью всех п-ок натуральных чисел, а основные операции Fi являются примитивно рекурсивными, то алгебра

называется примитивно рекурсивной. Теорема 4 может быть теперь переформулирована следующим образом: каждое рекурсивно перечислимое множество э,11ементов пртштивно рекурсивной алгебры порождает в этой алгебре рекурсивно перечислимую подалгебру.

Примеры и задачи

1. Каждое бесконечное рекурсивно перечпслимое ьшожество содержит бесконечное рекурсивное подмножество.

2. Проекции. Геометрически ге-ки чисел пстолковьшают обычно как точки га-мерного пространства; чпсла ij, . . ., i„ называют

координатами п-ш <х.у,. .., хп>. Пусть 1 < < . . . << ге. та-ку: <.х, . . ., > называют проекцией точки (х, . . ., 2;„> на коорди-

натную <ji, . . ., £т>-плоскость. Совоктшость проекций всех точек.! множества А на <ji, . . ., 1т>-плоскость называется проекцией множества А на эту плоскость.

Показать, что проекция рекурсивно перечислимого множества есть множество рекурсивно перечислимое и что каждое рекурсивно перечислимое -мерное множество есть проекция подходящего (п -{-} + 1)-мерного примитивно рекурспвпого множества.

3. Вещественное число а, имеющее вид

а = До + fli-lO-i + а2-10-2 -- . . .,

где flo, fli, . . . целые, О <Vj < 9 для i = 1, 2,. . ., называется ре-: курсивным (примитивно рекурсивным), если рекурсивна (примитивно рекурсивна) функция (х), определенная условиями

fa (0) = I flo Ь /„ + 1) = а.

Показать, что все алгебраические вещественные числа примитивно рекурсивны и что все рекурсивные вещественные числа образуют; алгебраически замкнутое поле.

Центральное понятие теории алгоритмов - это понятие функции, значения которой вычислимы с помощью алгоритма. Согласно тезису Чёрча (и. 2.3) алгоритмически вычислимые функции отождествляются с частично рекурсивными функциями. Настоящая глава посвящена доказательствам фундаментальных теорем о рекурсивных и частично рекурсивных функциях. Теоремы эти образуют основу теории рекурсивных функций.

§ 5. Общерекурсивные функции

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

5.1. Рекурсии 2-й ступени. Числа натурального ряда О, 1, 2, . . . образуют естественным образом упорядоченную последовательность. Эта упорядоченность играет фундаментальную роль в задании функций с помощью иримптпвной рекурсии. Именно, если определяемая функция многоместная, то из аргументов выбирается один, задается значение функции, когда этот аргумент равен О, п дается правило, как найти значение функции в точке г -}- 1, если известны ее значения при меньших значениях аргумента. Допустим теперь, что мы хотим аналогичным способом задать функцию двух аргументов F [х, у), но

ОБЩЕРЕКУРСИВНЫЕ

И ЧАСТИЧНО РЕКУРСИВНЫЕ ФУНКЦИИ

гл. Hi. ОБЩЕ- Й ЧАСТИЧНО РЕКУРСИВНЫЕ ФУНКЦИЙ

ХОТИМ вести рекурсию не но одному аргументу, а сразу но обоим. Тогда дш предварите.чьно долншы как-то упоря- дочить все нары чисел (х, у}. Конечно, упорядочивать их; можно многими способами. Остановимся на словарном упорядочении: пара <а;, у) будет считаться предшествующей паре <Xi, У1), если либо х < х, либо х - х, э. у <. < Ух. Выписывая пары в только что установленном порядке, получим

<0, 0>< <0, 1>< . . . < <1, 0>< <1, 1>< . . .

. . . < <2, 0>< <2, 1>< . . . (1)

В этом расположении пары вида <n, О) играют особую роль - у них нет непосредственно предшествующей пары, а пара <0, 0> вообще является начальной.

Вернемся теперь к функции F [х, у), которую дш хотим задать рекурсией сразу по двум аргументам. Принимая во внимание расположение (1), мы должны сначала задать F (О, 0), положив его равным некоторому числу а. Затем мы должны как-то выразить F {х, у) через значения этой же функции для предыдущих пар значений аргументов. Здесь возможны следующие случаи:

а) Требуется найти F (О, х). Предыдущие значения функции имеют вид F (О, у), где у <. х.

б) Требуется найти F [п -\- Предыдущие значения функции имеют вид F [п, х), где щ п, а х произвольно. В частности, если «предыдущие» значения функции F известны, то можно считать известныдш и значения выражений вида

F{h {п), g (х)), F [и {п), F iU in), g {X})), F (/1 («), F iU (n), F (/3 (n), X))), . . ., (2)

где /i (тг), g [x) - какие-либо наперед заданные функции, удовлетворяющие условиям

/г(тг)<п{ = 1,2, ...). (3)

в) Требуется найти F {71 -\- \, х + 1). Предыдущие значения функции F здесь дюгут быть следующих типов:

F[n\,h{x)),F[h {n),F{U[n),g[x))),

F ih {n), F{n + i, и {X))), . . ., (4)

где fi - наперед заданные функции, удовлетворяющие условиям (3).

§ 5. ОБЩЕРЕЮФСИВНЫЕ ФУНКЦИИ

Таким образод!, чтобы задать функцию F (х, у) рекурсией по паре переменных, дп>1 можем задать выражения для F {п + 1, 0), F (тг -f 1, ж -Ь 1) через члены вида (2), (4), а также задать функцию одной пере.менной F (О, х 1) и число F (О, 0). В полном объеме этот способ задания нам далее не потребуется. В частности, нам не будут нужны члены вида F (Д (тг), F (/2 (тг), F (/, (тг), х))) и аналогичной бо гее сложной структуры. Мы ограничимся рассдютрением лишь следующего способа, который только и встретится HaJt далее. Этот способ мы будем называть рекурсией 2-й ступени.

Определение. Пусть заданы всюду определенные функции

G (жо, Хх, . . Хп), Н (хо, Хх, . . ., Xi), h (х)

и всюду определенные функции fx (х), gj (х), удовлетворяющие требованиям

fi (х) < X, gj (х) < ж (г = 1, . . ., ттг; / = 1, . . ., к).

Говорят, что всюду определенная функция F {х, у) возникает из функций G, Н, 1ъ, fi, gj рекурсией 2-й ступени, если

F {п + i, X + Г) =

= G{n-\-l,x,F{fx {n),F{n + i,x)), F (/2 {п), F (/3 (тг), X + 1)), F (/, (тг), ж -f 1), . . .

...,F ifm (тг), X + 1)), F{n + l,0)= (6)

==H{n + i,F{gx (n), F (Г2 (тг), 0)), F {n, 0),

F{g, (тг), 0), . . .,Fig,{n), 0)),

F (0, X) = h (x)

для всех значений n, x.

Например, в п. 5.3 мы детально изучим функцию В (х, у), определенную схедюй

5 (тг -Ы, а: -Ь 1) = 5 (тг, 5 (тг -Ы, х)), 5 (тг -Ь 1, 0) = sgn, В {0,х) = 2-h х.

Сравнение этой схедш со схемой (6) показывает, что В (х, у) возникает рекурсией 2-й ступени из функций

G (тг, X, у) = у, fx (п) = тг, k (х) = 2 х,

Я (тг) = sgтг.