АЛГОРИТМЫ И МАШИНЫ ТЬЮРИНГА

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

Как уже говорилось, мы не ставили себе целью дать всеобщее определение интуитивного понятия алгоритма, но нами до сих нор не были описаны вообще никакие классы процессов алгоритмического характера, достаточные для вычисления всех частично рекурсивных функций. Правда, это сделать было нетрудно, так как уже простой анализ понятия частичной рекурсивности приводит к одному из таких классов. Однако этот класс получается довольно СЛ0ЖНЫЛ1. В настоящей и следующей главах будет описан ряд важных и естественных классов алгоритмов и каждый раз будет показано, что совокупность функций, вычпслтшх посредством алгоритмов рассматриваемого класса, в точности совпадает с совокупностью частично рекурсивных функцпп. Это даст нам ряд новых подтверждений тезиса Чёрча и вместе с тем много новых тонких свойств частично рекурсивных функций.

§ И. Словарные множества и функцпп

Описание важнейших классов алгоритмов производится в терлшнах теории слов в некотором алфавите. Начала ее бы.чп изложены в § 1. Теперь мы хотим продви-HjTb эту теорию несколько дальше с тем, чтобы понятия

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

11.1. Словарные множества. Пусть А = {а, . . . . . ., Яр} - какой-нибудь конечный набор символов. Обозначим через @д совокупность всех слов в алфавите А, включая и пустое слово А. Всевозможные подмножества совокупности в том числе пустое подмножество 0, будут называться словарными множествами в алфавите А. Мы хотим определить понятия рекурсивных и рекурсивно иеречислимых словарных мнон{еств. Это будет сделано двумя путями: сначала при помощи нумерации слов, а в следующем разделе и более прямым способом.

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

Номер пустого слова А полагаем равным нулю. Далее Б каком-либо порядке числами 1,2,...,/? нумеруем символы алфавита. Пусть at обозначает символ с номером i. По определению номером слова а = . . . аг, «г, назы-

ваем число

с (а) = ц -\- hp + . . . + isp-

Символалш с (й), an условимся обозначать алфавитный номер слова й и соответственно слово, имеющее номер п. Так как при фиксированном р каждое положительное число представимо и лишь одним способом в виде

п = ig + hP + . . . + isp (1 < а < Р),

то каждое число есть алфавитный номер одного и только одного слова совокупности ©л. Разложение (2) иногда называется р-ичным разложением числа п с цифрами 1,2 . . р в от.чичие от обычного р-пчяото разложения, в котором в качестве коэффициентов допускаются числа О, 1, . . ., р - 1.

Множество слов ?И в алфавите А называется примитивно рекурсивным, рекурсивным пли рекурсивно перечислимым, еслп соответственно пртштпвно рекурсивна, рек5ф-спвна или рекурсивно неречислима совокупность алфавитных номеров всех слов пз Ш.

Принимая во внимание результаты нп. 4.1 п 4.2, непосредственно видим, что

а) каждое конечное множество слов примитивно рекурсивно;

j.-- б) объединение и пересечение конечной системы примитивно рекурсивных, рекурсивных или рекурсивно неречислимых множеств слов суть множества того же типа;

с) если словарное множество и его дополнение ©л - - Ж рекурсивно иеречиспимы, то они рекурсивны.

Говорят, что в алфавите А задана частичная м-местная словарная функция F, если некоторым п-кш 5i> • • м ?п слов из ®А поставлены в соответствие однозначно определенные слова F {Ху, . . ., р„) в А (ср. п. 1.2). Числовая ?г-местная частичная функция / называется функцией, представляюш;ей словарную функцию F в нумерации а, если

F {axi, . . ., ахп) = af (ху, . . ., Хп) для всех натуральных Ху, , . Хп и, следовательно, - (fi,. • •, fn) = а/ (cfi,..., Cf„), (3)

f(xi, ..., Хп) =e{F(axi, ..., ax)). (4)

Очевидно, каждая частичная словарная функция обладает единственной представляюш;ей функцией и каждая частичная числовая функция представляет определенную словарную функцию.

Частичная словарная функция F называется примитивно рекурсивной, общерекурсивной или частично рекурсивной, если таковой является числовая функция, представляющая F.

Например, постоянные словарные функции представляются постоянными числовыми функциям. Постоянные числовые функции примитивно рекурсивны. Поэтому постоянные словарные функции примитивно рекурсивны.

Докажем еще примитивную рекурсивность простейших словарных Фзгнкции St (г), определяелшх формулами

Si (?) = (i = 1, . . ., р).

Согласно (4) представляющей фзнкцией для 8i (р) является функция

Si {х) = с {ах-at). Из формулы (1) непосредственно видно, что

с (гаг) = рс (г) -f j (5)

п нотому

Si {х) = рх -\- i.

Таким образом, представляющие функции для словарных (()ункций;8,- примитивно рекурсивны, а вместе с ними будут примитивно рекурсивными и сами словарные функции.

Аналогичным путем легко доказать примитивную рекурсивность функции F (у, ?)) = fJ) и многих других, которые нам повстречаются далее. Однако здесь мы это делать не будем, так как в следующем разделе это получится еще более просто.

Введенные только что определения рекурсивности, частичной рекурсивности словарных множеств и функций паиисят от первоначальной нзгмерации алфавитных символов. Кроме того, возникает вопрос: если множество Ш слов в алфавите А, например, рекурсивно, то будет ли Ш рекурсивно и в произвольном расширении алфавита 4?

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

Теорема 1. Рассмотрим какой-нибудь алфавит Л = [ау, . . .,ар) и его расширение Ау = {а, . . ., а, а,,.+1, . . ., а}. Совокупность ?К некоторых слов в алфавите А тогда и только тогда примитивно рекурсивна, рекурсивна или рекурсивно перечислима в А, когда она ижет тот же тип в А.

Частичная словарная функция F (fj, . . ., f„), определенная в алфавите А, частично рекурсивна в А тогда и только тогда, когда она частично рекурсивна в Ai.

Всюду определенная на ©л словарная функция F примитивно рекурсивна или рекурсивна в А тогда и только тогда, когда F может бить доопределена до примитивно рекурсивной или соответственно рекурсивной функции е Ау.

Докажем сначала первое утверждение. Обозначим через а, словарные нумерации совокупностей ®д, ©л,. Ана.логично, еслп й - слово в алфавите А, то через с (й) обозначим его а-номер, а через ву (й) - ау-поиер. Покажем, что фзнкция / {х) ~ Су (ах) примитивно рекурсивна.

Пусть X > О, ах ~ л. Представляем й в виде bat.

Из (5) и (6) пол5П1а

х = рс (Ь) 4- г, Ci (ЬаО = (Ь) + i,

откуда

/ [х) = qf {[xip] sg rest {х, р)) + [хр [xIpVj +

+ р sg rest (а:, р).

Это соотношение можно рассматривать как возвратную рекурсию для / [х) и потому в силу и. 3.2 функция / {х) примитивно рекурсивна.

По оиределению / (ж) есть «х-номер слова, имеюнего а-номер, равный х. Но тогда ясно, что число

/* (х) = \y(,x-t (у) = 0) (7)

есть а-номер слова, имеющего а-номер, равный х, ири условии, что такое слово существует. Если же такого слова нет, то формула (7) все же дает некоторое значение для /* (х). Поскольку /* (х) < а;, то в силу и. 3.1 заключаем, что функция /* {х) примитивно рекурсивна.

Перейдем теперь к доказательству первого утверждения теоремы. Рассмотрим какое-нибудь множество 5Ш слов из ®А, примитивно рекурсивное в А. Это означает, что совокупность «х-номеров слов из 5К совпадает с совокупностью всех решений уравнения вида v (х) = О, где

V (х) - подходящая примитивно рекурсивная числовая функция. Но тогда совокупность всех а-номеров слов из Ж будет совпадать с совокупностью решений уравнения

V (/ (х)) = О, левая часть которого является иртштивно рекурсивной функцией от х. Следовательно, множество примитивно рекурсивно в нумерации а.

Обратно, пусть множество Ж примитивно рекурсивно в нумерации а и совокупность решений уравнения v (х) = = О теперь является совокупностью ос-номеров слов из . Обозначим через 31 множество тех слов из ©л,, а-номер у которых удовлетворяет уравненпю

V (/* (у)) = 0.

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

Поэтому остается доказать лишь примитивную рекурсивность ©4 в нумерации «1. Но coBOKjTinocTb а-номеров слов из ©л совпадает с совокшностью всех значений функции / (а;). Так как эта функцпя примитивно рекурсивна и

удовлетворяет условию / (а;) > а;,Что но теореме 3 из п. 4.1 совокупность значений / примитивно рекурсивна, что и требовалось.

Итак, примитивная рекурсивность множества слов в нумерации aj равносильна примитивной рекурсивности Ж в нумерации а. Остальные утверждения теоремы 1 доказываются тем же методом.

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

Пусть алфавит А состоит из букв а, . . ., ар. Словарные функции О, Jm (i = 1, . . ., р; m < и; т, п = 1, 2, . . .), определенные в алфавите А равенствами

0(?) = Л, 5fi(f) = №, f2, . . ., P„) = fm,

условимся называть простейшими. Из и. 11.1 неносредственно следует, что простейшие словарные функции при-.\гитивно рекурсивны.

Пусть в алфавите А заданы частичная словарная функция G от п переменных и частичные словарные функции 1, . . ., Gn, каждая из которых зависит от одного и того же числа }п переменных. Символом Sf+i (G; G, . . ., G„) обозначаем частичную словарную функцию F от т переменных, определяемую обычной формулой

Обозначим через g, g, . . ., gn, f представляющие (Ьнкции (п. 11.1) для словарных функций G, G, . . . . .,Gn, F. Пз (1) непосредственно следует, что для любых натуральных х, . . ., Хщ

f {Хх, . . ., Xjn) = g [gi. {Хх, . . ., Хт), . . gn {Хх, . . ... Х,п)),

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