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

1. Пусть N - совокупность натуральных чисел, + - обычная арифметическая операция сложения чисел. Показать, что в алгебре Ш = <N; -j- > число 2 порождает мнон{ество всех положительных четны.х чисел, число I порождает множество всех поло житель- . ных чисел, а числа О и 1 порождают всю алгебру St.

2. Показать, что все подалгебры алгебры SB == <iV; -f-, -> исчерпываются следующими: а) подалгебра (0), порожденная числом О и состоящая только пз пего; б) подалгебра (1), порожденная числом 1 п совпадающая с caMoii алгеброй в) подалгебра (а), порожденная произвольным числом а >> 1, состоящая пз чисел О, а, 2а, За, . . .

3. Показать, что каждая подалгебра алгебры 21 = <iV; -[- > состоит из всевозможных кратных подходящего числа а, возможно, за исключением конечного числа таковых.

4. Рассмотрим алгебру S=<iV; -]-,•,- >, где операция «-» рассматривается как частичная двуместная операция. Значение терма X - у считается равным обычной разности для х и неопределенным для X < !/. Какие функции представляются термами 0-{х - {х+ 1)), (х - у)+ у, {х+ у) - у? Показать, что функция 2 не мо?кет быть представлена термом в алгебре S (т. е. термом, записанпым в алфавите х, +, •, -).

§ 2. Основные вычислимые операторы

Операции над числовыми функциями далее называются операторами. В настоящем параграфе определяется ряд операторов, обладающих тем свойством, что, применяя их к функциям, вычислимым в интуитивном смысле (см. введение), мы получим функции, также заведомо вычислимые в интуитивном смысле. Частичные функции, которые можно получить при помощи этих операторов из простейших функций S (х) = X + I, о (х) - О, Im (х, . . ., Х) =

= Xjn, называются частично рекурсивными. Основная гипотеза Чёрча состоит в том, что класс частично рекурсивных функций совпадает с классом функций, допускающих машинное или алгоритмическое вычисление.

2.1. Суперпозиции частичных функций. Пусть заданы п каких-либо частичных функций /i, . . ., /« от одного и того же числа пг переменных, определенных на каком-то множестве А со значениями в дшожестве В, п пусть на множестве В определена частичная функция / от п переменных, значения которой принадлежат некоторому третьему дшожеству С. Вводим теперь частичную функцию g от т переменных, определенную на А со значениями в С, полагая по определению

g {Хх, Xm)=f (/i {Xi, . . ., Хт), . • .fn (Xi, Xm))

для произвольных Xi, . . ., Xm ИЗ A. Говорят, что функция g получается операцией суперпозиции или подстановки из функций /, /х, . . ., /„. Операция подстановки будет далее обозначаться символом /S""*". Индекс сверху означает число функций. В качестве множеств А, В, С ниже почти всюду будет браться множество натуральных чисел Ж. Условимся через о"" обозначать совокупность всех частичных числовых функций от п переменных. Оператор S" является всюду определеннойфункцией из X g" X ... X в g-"". Если же рассматривать множество % всех частичных числовых функций от произвольного числа переменных, то оператор S" можно рассматривать как частичную функцию от тг -f 1 переменной, определенную на % со значениями в %. При этом терм S"" (/, fi, . . ., /„) имеет определенное значение (равное частичной то-местной функции) тогда и только тогда, когда значением переменной/будет ?г-местная функция, а значениями символов ft, . ., fn будут частичные функции от одного и того числа переменных. Например, с последней точки зрения значение терма 8 1\, ll) не определено, а значение терма l\, l\) равно Ii,

где ll, l\, ll - символы простейших функций, определенных в п. 1.2.

Всоответствии с п. 1.3 система р, состоящая из совокупности функций % и определенных на ней частичных, операций 8", 8, . . будет частичной алгеброй.

Пусть /х, . . ., /"s - какие-нибудь частичные числовые функции соответственно от щ, . . ., Us аргументов («1, . . ., Us произвольны). Частичные функции, которые можно пол5П1ить операциями подстановок из /", . . ., п функций 1т (т, /г = 1, 2, . ..), называются элементарными относительно /", . . ., /s. Совокупность их будет в алгебре sp подалгеброй, порожденной элементами /", ...

• м /s /т. Теорема 1 из п. 1.3 показывает, что относительно элементарньгашбудут те и только те частичные функции, которые можно записать в виде термов, содержащих функциональные символы 8", 8, . . . операций подстановки, СИМВ0.ЧЫ /", . . ., заданных и символы Простейших функций. Однако для относительно элементарных* функций" возможна и еще более простая Запись.

Теорема 1. Для того чтобы некоторая п-местная частичная числовая функция f была элементарной относительно частичных функций fi, . . ., fs, необходимо и достаточно, чтобы / можно было представить в виде терма, записанного с помощью функциональных символов /ц /г, .. • • • ,fs,ImU некоторых предметных переменных xi, . . ., х» часть из которых может входить в терм и фиктивно.

Итак, утверждается, что для относительно элементарной частичной функции / существует две записи: 1) в виде значения терма, функциональными символами которого служат символы S операций подстановки, а предметными символами - символы /i, . . ., fs, Im (термы этого вида мы будем называть операторными); 2) в виде терма (а не значения терма), составленного из функциональных символов fl, . . , fs И некоторых предметных переменных (может быть, фиктивных). Эту запись мы будем называть.; термальной записью. Отметим еще раз, что в первом слу-: чае функция / есть значение терма, а во втором функция / представляется термом.

Для доказательства теоремы надо показать, что от термальной записи можно переходить к операторной и наоборот. Пусть / - значение операторного терма а. Если длина й равна 1, то й есть либо либо В первом случае термальным представлением для / является терм (а:;,, . . . . . ., Xi ), а во втором слугчае - терм Xj. Если длина л: больше 1, то й имеет вид S+ {Ь, bi, . . ., h), где b,bi, . . . операторные термы дгеньшей длины. По индукции предполагаем, что термальные представления

С = с{х1,...,х,,.), Ci=Ci(xi, . . . ,Хп) (i = i,...,k) значений термов Б, Ьх, . . ., нам известны. Тогда с (Ci.(a;i, . . ., х.„), . . . , С. {xi, X,,)) будет искомым термальным представлением для заданного операторного терма й.

Обратно, пусть ?г-местная частичная функция / задана своим термальным представлением й (х, . . ., х), где переменные а;,,, . . ., xi. фактически входят в"" терм, а остальные из переменных х, . . ., х рассматриваются как фиктивные. Если д.чпна терма й равна 1, то й имеет вид Xj- и, значит, / равна значению операторного терма ij. Если же длина терма й больше 1, то й имеет вид (й1, . . . . . ., й„.), где Й1, . . ., йп. - термы меньшейдлины. По ин-

дукции предполагаем, что для каждой п-местной частичной функции от Xi, . ..,Хп, представляемой термом й, найдено ее выражение в виде операторного терма Cj (/ = = 1, . . ., щ). Тогда ясно, что функция / будет значением операторного терма S"*- (/,-, q, . . ., с„.).

Например, пусть заданы обычные функции -f и х. Функция от Xi, х, Хд, имеющая термальное представление Xi-xХз, является значением операторного терма

s{+,sx,n,n),il).

2.2. Оператор примитивной рекурсии. Пусть заданы какие-нибудь числовые частичные функции: ге-мест-ная g VI (п + 2)-местная h. Говорят, что (п + 1)-местная частичная функция / возникает из функций g и h примитивной рекурсией, если для всех натуральных значений

Xi, . . ., Хп, У

f.{Xi, . . ., Хп, 0) = g{Xi, . . ., х„), (1)

/ {xi, . . ., Хп, у -\- 1) = h {х, . . ., Хп, у, f{Xi,..., Хп, у)}.

Это определение мы будем применять и для п = О, говоря, что одноместная частичная функция / возникает примитивной рекурсией из постоянной одноместной фушк-ции, равной числу а, и двуместной частичной фзгнкции h, если

/(0) = а, (3)

fix + i) = h{x,f (х)). (4)

Встает вопрос, для каждых ли частичных функций g, h от п и п 2 переменных существует частичная функция / от 71 4- 1 неременной, удовлетворяющая условиям (1), (2) или соответственно (3), (4), и будет ли такая частичная функция единственной? Так как область определения функций есть множество всех натуральных чисел, то ответ на оба вопроса, очевидно, полож-ителен. Если фущкция / существует, то из (1) и (2) последовательно находим

/ (Xi, . . .,Хп,0) = g (Xi, . . „ Хп),

/ (Х, . . .,Хп, 1) = h (Xi, . . ., Хп, О, g (Xi, . . ., Хп)),

f ii, . . ., Zn,m + i) = h{xy, . . .,Xn, m,f{xi, . . ., x, m))

и потому / определена однозначно. Из соотношений (5), в частности, видно, что если для некоторых х, . . Хп, t значение / {х,. . ., Xn,t) неопределенное, то неопределен-нылш будут и значения / (х-, . . Хп,у) для всех у t.

Чтобы при заданных частичных функциях g, h найти функцию /, возникающую из них примитивной рекурсией, достаточно равенства (5) принять в качестве равенств, определяющ;их значения функции /. Таким образом, для любых частичных ге-местной функции g и (тг + 2)-местной функции h [п = О, i, 2, . . .) существует одна и только одна частичная (тг + 1)-местная функция /, возникающая из g и /г примитивной рекурсией. Символически пишут

и рассматривают К как символ двуместной частичной one- ; рации, определенной на множестве % всех частичных 1 функций. Из соотношений (5) вытекает, что если функции g я h всюду определены, то и функция/ всюду определена, i

Из соотношений (5) видно также и следующее фундаментальное для нас обстоятельство: если мы каким-то * образом «умеем» находить значения функций g, h, то значения функции / можно вычислять при помощи процедуры вполне «механического» характера. Именно, для нахождения значений / {ах, . . ., а„, ттг + 1) достаточно последовательно найти числа

Ъх h {ах, . . ., On, О, bo), Ьч = h {ах, . . ., On, 1, bx),

bm+l = h К, • • •, «n, bjn)-

Полученное на (тп + 1)-м «шаге» число Ьтп п будет иско-1шм значением функции в точке (aj, . . ., а„, тп + 1>. Изложенный процесс вычисления / {ах, . . ., а„, ттг + 1) будет продолжаться неограниченно только в том случае, когда неограниченным окажется процесс вычисления одного из выражений

g {ах, . . ., On), h {их, . . ., On, О, 6о). • • •

. . .,h {ах, . . ., On, т, Ьт),

т. е. когда хотя бы одно из этих выражений будет иметь неопределенное значение. Но тогда в соответствии с определением фзгнкции / значение / {ах, . . ., а, т + 1) будет неопр еде леннБШ.

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

S, о, fin. конечным ЧИСЛОМ операций подстановки и примитивной рекурсии.

Функция / называется просто примитивно рекурсивной, если ее можно получить конечным числом операций подстановки и примитивной рекурсии, исходя лишь из простейших функций S, о, Im.

Операции подстановки и примитивной рекурсии, будучи применены к всюду определенным функциям, дают в результате снова всюду определенные функции. Поэтому, если задана система © всюду определенных функций, то примтивно рекурсивные относительно @ функции всюду определены. В частности, все примитивно рекурсивные функции всюду определены.

Ясно, что частичная функция /, примитивно рекурсивная относительно какой-нибудь системы © частичных функций, примитивно рекурсивна и относительно любой более широкой системы. Примитивно рекурсивные функции можно рассматривать как примитивно рекурсивные относительно пустой системы @. Поэтому примитивно рекурсивные функции - это функции, примитивно рекурсивные относительно любой системы функций.

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

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

Согласно определению одноместные функции s {х) = ~ X -\- I, {х) = О, li {х) - X и лшогоместные функции

/т {хх, . . ., Хп) = Хт {т, тг = 1, 2, . . .) пртштивно рекурсивны.

Для тг-местной функции о" {хх, . . ., Хп) = О имеем представление

о- = 8Цо\П)