Содержание к диссертации
Введение
ГЛАВА I. Основные понятия 18
I. Примитивные программные алгебры /ШІА/ 18
2. Примеры ППА 23
ГЛАВА II. Полнота в основных классах вычислимых функций 25
3. Полнота ШІА в основных классах арифметических вы
числимых функций . 25
4. Слабые и ограниченные ІША. Изоморфизм ППА 38
5. Полнота ППА в основных классах целочисленных вы числимых функций 42
6. Полнота ППА в основных классах рациональных вы числимых функций 50
7. Полнота ППА в основных классах словарных вычисли мых функций 62
ГЛАВА III. Алгебраические свойства арифметической ППА . 71
8. Расширенные ППА п -арных функций и предикато 72
9. Взаимная непроизводность основных операций ариф метической ППА и смежные вопросы 74
10. Некоторые подалгебры арифметической ППА 90
Заключение... 104
Литература
- Примеры ППА
- Полнота ППА в основных классах целочисленных вы числимых функций
- Полнота ППА в основных классах словарных вычисли мых функций
- Взаимная непроизводность основных операций ариф метической ППА и смежные вопросы
Введение к работе
Одна из актуальных задач современной теории программирования заключается в формализации семантики языков программирования. Из-за сложности этой задачи возникло несколько различных методов ее решения /см., например,[ 6^]/. Предлагаемая'работа основывается на композиционном подходе, заложенном в работах В.Н.РедькоГ^-^J.
В рамках композиционного метода было достигнуто не только существенное продвижение в формализации семантики языков программирования /см., например,[30, 5]/, но и реализован ряд систем программирования, например, система автоматизированного построения процессоров ДЕФИПСГ6 , /ЗІ*
Сущность композиционного подхода раскрывается в его принципах!^ ], среди которых мы отметим принцип функциональности и принцип композиционности.
В силу первого принципа семантикой любой программы является функция, отображающая множество исходных данных в множество результатов. Т.о., в качестве семантики языка программирования, рассматриваемого как класс программ, выступает соответствующий класс функций.
По принципу композиционности для описания таких классов функций необходимо рассматривать алгебры функций, называемые в этом случае программными алгебрами /ПА/, замыкания в которых и будут задавать упомянутые классы функций.
В [60 ~/ ] была построена иерархия ПА, оправданность рассмотрения которой вытекает из большого разнообразия языков программирования, а, значит, и ассоциированных с ними классов функций.
Верхний уровень этой иерархии составляют фундаментальные ПА, нижний - примитивные ПА /ППА/, в качестве примера ПА промежуточного уровня укажем на элементарные ПА L //, 30]. При этом выделение ППА связано с тезисом об их полноте в основных классах /эффективно/ вычислимых функций [V/ J.
Целью диссертационной работы как раз и является обоснование этого тезиса, т.е. вскрытие алгебраической структуры различных классов вычислимых функций на основе ППА; кроме того, будут исследованы и сами ППА.
Отметим, что в литературе неоднократно рассматривались различные алгебры вычислимых арифметических функций /т.е. функций натуральных аргументов и значений/; что же касается алгебр других классов функций, то здесь можно только отметить результаты А.Й.Мальцева и И.Д.Заславского по характеристике класса словарных частично рекурсивных функций У^,^] /А.И.Мальцев, кроме того, рассмотрел алгебру словарных примитивно рекурсивных функций /e,II.3lW1//9 а также работы [^ )??] , в которых рассматривались алгебры унарных вычислимых функций в множестве кортежей, составленных из натуральных чисел.
Между тем, в литературе вводились вычислимые функции, отличные от "традиционных" вычислимых арифметических и словарных функций; например, рассматривались /как правило, без вскрытия алгебраической структуры соответствующих классов функций/ вычислимые функции в следующих областях:
— в — а/ множество кортежей, составленных из натуральных чисел
6/ множество кортежей, составленных из слов конечного алфавита
в/ множество конечных графов /комплексов/ [3?, ?б\ \
г/ множество конструктивных действительных чисел I ^? J;
д/ множество арифметических функций /гл. 101 3^ \% 9.8 [62 ]/, более того, можно рассматривать вычислимость на функционалах и более высоких типов /рекурсия в высших типах [36 ]/.
Конечно, список примеров можно продолжить /см., например, [М 1/> еще больше примеров дают языки программирования.
Итак, имеются разнообразные классы вычислимых функций /выше приведены конкретные примеры таких классов, по поводу абстрактного подхода к вычислимости в различных областях см. обзоры А.П.Ершова l-6\/щ Поэтому изучение алгебр, одинаково пригодных /!/ для вскрытия структуры различных классов вычислимых функций, представляет несомненный интерес, в том числе и для общей теории вычислимых функций. Что касается ППА, то, забегая наперед, мы покажем их полноту в классах арифметических, целочисленных, рациональных /т.е. функций, аргументы и значения которых суть рациональные числа+//, словарных частично, обще- и примитивно рекурсивных функций.
Точное определение ППА будет приведено в гл. I, здесь же ограничимся неформальным обсуждением.
ППА имеет всего три параметрических операции: суперпозицию, ветвление и цйклирование. Суперпозиция близка по существу к
+' Не путать с понятием целой рациональной функции в алгебре.
- г -
одноименным операциям, рассматривавшимся в литературе; ветвление -аналог кусочного задания функций; циклирование - аналог простейшей циклической констукции языков программирования типа do кгкщ.^ простота при этом заключается в том, что, грубо говоря, оператор тела цикла может менять значение только одной переменной. Принципиальная особенность этих операций состоит в их независимости от
типа аргументов и значений функций, к которым они /операции/ при-
+/
меняются. '
Формализмы, явно или неявно пригодные для вскрытия алгебраической структуры многих классов вычислимых функций, предлагались и ранее; для мотивировки введения ППА ниже будет дан их обзор. Подчеркнем, что речь будет идти о вскрытии структуры классов вычислимых функций, уже определенных тем или иным способом /по поводу таких способов см. уже упоминавшиеся обзоры А.П.Ершова/.
Первыми здесь следует назвать логические схемы программ А.А.Ляпунова граф-схемы Л.А.КалужнинаІ^З ]. Так как в этих работах почти не рассматривались способы построения одних логических схем /граф-схем/ из других /за исключением операции подстановки граф-схемы I рода в граф-схему же/, то единственный способ извлечения операций состоит в связывании с каждой логической схемой /граф-схемой/ соответствующей операции. Но, в виду допущения логических схем и граф-схем любой сложности4"^ сигнатура алгебр, построенных таким путем, будет очень сложной.
+' Например, суперпозиция в обычном смысле обладает такой независимостью, в то время как примитивная рекурсия и минимизация /в классе арифметических функций/ - нет.
++' Т.е., из-за неструктурированности этих объектов.
Не рассматривались bL«^ ,^/ J и вопросы полноты /Ji.A.Ka-лужнин ограничивается неформальным обсуждением/, однако развитие идей, заложенных в этих работах, привело в дальнейшем к построению соответствующих алгебр и изучению их полноты.
Переходим к операторным алгорифмам А.П.Ершова Отметим, что модели, по существу совпадающие с операторными алгорифмами, неоднократно вводились различными авторами (ДГ ]; сюда следует отнести и различные "машинные" подходы \3^ 35 52 #\.
В определении класса операторных алгорифмов U (ч ^) фигурирует параметр Л - некоторое множество "простейших" операций. Именно из этих операций строятся все операторные алгорифмы упомянутого класса. Т.о., варьируя параметр ^С , можно получать различные классы операторных алгорифмов, а, значит, и различные классы функций, реализуемых ими.
Так, А.П.Ершов исследовал полноту операторных алгорифмов в классах арифметических и словарных вычислимых функций. Отметим, что при этом для задания вычислимых словарных функций в некотором алфавите приходится рассматривать операторные алгорифмы уже над этим алфавитом"1"'.
ъ[2^ ]не рассматриваются способы построения одних алгорифмов из других /кроме композиции алгорифмов, аналогичной подстановке граф-схем Л.А.Калужнина/, поэтому отсюда извлечь нетривиальные операции в множестве функций не удается. Однако уже в работе И.Д.Заславского I <Р ./такие операции имеются.
Центральное понятие этой работы - граф-схема с памятью.
+' Для задания этого класса использовались нормальные алгорифмы А.А.Маркова\46\ для которых, вообще говоря, необходимо расширять алфавит [5Ї ]. в[такое расширение алфавита не требуется.
Граф-схемы с памятью близки к граф-схемам Л.А.Каяужнина и к операторным алгорифмам А.П.Ершова так называемого нулевого ранга /т.е., говоря содержательно, не меняющимся в процессе работы/.
Для нас важен результат И.Д.Заславского о совпадении граф-схемного замыкания множества функций и предикатов /т.е. множества функций и предикатов, реализуемых граф-схемами, построенными из функций и предикатов исходного множества/ с его нормальным замыканием. При этом под нормальным замыканием понимается замыкание с помощью операций, получаемых из восьми схем операций, и трех ноль-арных операций. Т.о., по существу построена алгебра с квазиконечной сигнатурой.
Операции ППА близки к некоторым из операций нормального замыкания; в частности, аналогом циклирования ППА является операция повторения I рода функций /функторов по терминологии І 2*1/ по предикату. Существенное отличие между этими операциями состоит в том, что при циклировании, грубо говоря, меняется значение только одной переменной, а при повторении I рода - в общем случае нескольких.
Отметим, что ИД.Заславский установил полноту граф-схем с памятью в классах вычислимых арифметических и словарных функций.
Итак, отмеченные выше модели можно использовать для задания классов вычислимых или, говоря более точно, частично рекурсивных функций. Однако представляется невозможным их прямое применение для задания классов общерекурсивных функций. Что же касается субрекурсивных классов, то здесь следует упомянуть задание арифметических примитивно рекурсивных функций при помощи интерпретированных так называемых Sttp -схем - частного случая граф-схем с памятью Г 80 J/cm. также п.II.7 гл. ІУ п. г [ ?5 1 и
ю -
[69 ]/+'. Особенность интерпретированных Step - схем состоит в том, что каждый их оператор цикла выполняется заранее известное конечное число раз, равное значению выделенной переменной перед выполнением этого оператора. Как видим, s-ієр - схемы ориентированы на арифметические функции. Забегая наперед, отметим, что при задании примитивно рекурсивных функций, не обязательно арифметических, с помощью ЇЇПА мы используем аналогичную идею.
Для классов унарных функций предлагались свои особые модели. Здесь сначала отметим системы алгоритмических алгебр /САА/ В.М.Глушкова и-^ 1, САА является двухосновной алгеброй, сигнатура которой состоит из семи операций над унарными операторами и условиями. Между ограничениями операций ППА на множество унарных функций и предикатов и операциями САА - умножением, j3 -дизъюнкцией, cL - итерацией, - существует тесная связь /отличия только в деталях/.
Переходя к полноте САА, укажем на результат Ю.В.Голункова по полноте САА в классе унарных вычислимых арифметических операторов и условий
Для характеристики классов унарных вычислимых функций также можно использовать операторные алгоритмы по терминологии п.14.3 книги А.И.Мальцева Ш ]/в более ранней работе Я.М.Бард-зиня!. /? J используется термин "М-операторы"/. Такие операторные алгоритмы близки к интерпретированным граф-схемам Л.А.Калужнина, а также к граф-схемам И.Д.Заславского, память которых состоит из одной переменной.
+' Более того, bL^ , № J подтверждается известная иерархия А.Гжегорчика
-. и -
Как и для операторных алгорифмов А.П.Ершова, в указанных работах не разрабатывались способы построения одних операторных алгоритмов из других, поэтому непосредственно извлечь интересные операции здесь не удается. Но можно учесть очевидную связь операторных алгоритмов с интерпретированными граф-схемами Л.А.Ка-лужнина и воспользоваться результатами работы\?i Jno структуризации диаграмм. Однако на этом пути мы получим, по сути операции ЕАА для унарного случая.
Отметим полноту операторных алгоритмов в классе унарных арифметических частично рекурсивных функций /теорема 2 п. 14.3 и теорема 3 п. 15.2
Завершая обзор, укажем также на близость между операциями ППА и операциями над нормальными алгорифмами /гл. Ш 5, ы.46 ]/, а также операциями, введенными в
Итак, операции ППА имеют ряд аналогов; конечно, точные взаимосвязи могут быть прослежены только после формального определения ППА, что и будет сделано в гл. I.
Перейдем к структуре и содержанию диссертационной работы. Она состоит из введения, трех глав, заключения, списка литературы и приложения. Главы состоят из параграфов, а параграфы г- из пунктов. Для параграфов принята сквозная нумерация, нумерация лемм и теорем в каждом параграфе своя. Для ссылок используется двойная нумерация, например, "лемма 2,1" - это первая лемма 2, а "п.3.3" - третий пункт 3. При ссылках внутри параграфа первый номер /номер параграфа/ будет опускаться.
Распределение материала следующее. В 1 гл.1 вводится центральное понятие - понятие примитивной программной алгебры /ППА/. В 2 этой же главе строятся четыре конкретные ППА: ариф-
- Y& -
метичеекая, целочисленная, рациональная и словарная ППА. Их носителями являются, соответственно, классы всех арифметических, целочисленных, рациональных и словарных функций, зависящих от конечного числа переменных. Кроме того, в 2 приводятся примеры построения функций в арифметической ППА.
Примеры ППА
В этом пункте мы покажем, что любую чрф /и только такую функцию/ можно построить в арифметической ППА. из ноль-функции О foe) , функции следования sfx) , сложения Х.+Ц , умножения xy , предиката строго меньше х х% и тождественных функций, Множество этих функций обозначим, как и во введении, через 6±.
Основной результат /теорема I/ будет получен в качестве непосредственного следствия ряда лемм. Лемма I. Функция J-/Ьс„ ..., ,), получающаяся из функций i5 -- ij .-y 4"vj -v J операцией суперпозиции g(»t+-() адресе чрф, может быть получена из тех же функций суперпозициями арифметической ППА. Действительно, очевидно, что Чтобы не выходить из рассматриваемого класса функций, под предикатом условимся понимать функцию, значениями которой могут быть только О или / , интерпретируя О как А а / -как U . Буквы р,$,,» возможно с индексами, будем использовать в качестве предикатных символов. Лемма 2. Функция fxf/...txK) , получающаяся операцией минимизации из функции Я/х уХ ) , может быть получена в арифметической ППА из функций &(&#...,Х oficjj Sflc)у тождественных функций и предиката неравенства х,фх . Доказательство По условию, для любых ..v . Лемма 3. Функция / ,...,- /) » получающаяся операцией примитивной рекурсии из функций jZf -ryv -г у/ и Afe;... -Z t/ &) » может быть получена в арифметической ППА из функций /.v- Jy / /-у-2 / / / тождественных функций, канторовских нумерационных функций / / /7} и предиката зо, JC%. Доказательство
По условию для любых -. Положим /ofa.., Ю -у )у 1 &&))= Далее, пусть / Г/к) у= fe у г/ Ху) Нетрудно проверить, что так построенная функция/ ... (/,%) и исходная функция/ .., x yj связаны следующим образом: Лемма 4. Функция У/ „..., / , получающаяся суперпозицией "" " з $1 /оґ . і/, может быть получена из этих же функций и селекторных функций суперпозициями у = 4-, Доказательство По определению суперпозиции Обозначим через 1 «(u ..., Uf)y /s$ селекторную функцию /т.е. У /- /) / / и рассмотрим следующие функции, полученные введением фиктивных аргументов: / » v « (УьСЪг-, %Л I % , щ , 1 % М Теперь очевидно, что Jfa„. yUt)= S fjfofa-jX ), A U,;... ... kjlfa-./t/j), где -7-- ЄСЛИ Xj-p /2 ,..., J, Фиu"=l$p(u"- u } еоли зу=4рУр=Р ;п Отсюда непосредственно вытекает Следствие I. Классы чрф, орф и прф замкнуты относительно суперпозиции . Лемма 5. функция /..., бр) » получающаяся из функций afcCfj... ) и J-ft/fj. -sysn) fe/%) - циклированием, может быть получена из функций ffiftx ... ЯГА)у jpfyv-fln); OfeX, s и селекторных функций операциями суперпозиции & с у =/,2,.., примитивной рекурсии и минимизации. Доказательство В силу определения циклирования/ ..у - faj xdUfy,. ., ] . кроме ТОГО, ///, ,// /; поэтому положим j r- , K f,/71 Очевидно, что если %-ф / --7- } » то функция -f0(fi-, g) удовлетворяет кусочной схеме I неопределено иначе для всех &f, ... І . Т.о., в этом случае утверждение леммы верно, и остается рассмотреть оставшийся случай -/-2 ...,- положим Z = JCrj ={7г . Теперь рассмотрим функцию h ъ—,У/п,у) » удовлетворяющую схеме примитивной рекурсии: iff,-- ) = , для всех Уи..:,р»с,р.
Очевидно, функция /y —jy njу) получается примитивной рекурсией из функций I Yft, -,&), &%, -,/».,/, fc/fy,j ...,/„, ,Ух« # ) Далее, положим Нетрудно проверить, что v , "vУъ ь) есть і -тнй элемент ,{„...,їс) " последовательности, a / /4,..., j равно номеру -f0( r / XJ - элемента, если он существует /в противном случае (,..., ) не определено/ для всех ,..., и U0, ,Z,..! /следовательно,
Полнота ППА в основных классах целочисленных вы числимых функций
В этом параграфе мы дадим алгебраическую характеристику в ППА. классов целочисленных чрф, орф и прф. Начнем, следуя п.II.1С ]и 5 гл.іГ І с определения таких функций.
Пусть - эффективное взаимно-однозначное отображение множества натуральных чисел на множество целых чисел, т.е., по терминологии п. 9.1 Г ], й - эффективная однозначная простая нумерация множества целых чисел /в дальнейшем, говоря о нумерациях, будем иметь в виду именно такие нумерации/.
Целочисленная функция называется чрф, орф или прф, если - 3 такой является арифметическая функция, представляющая4" эту функцию в нумерации Z .
Конкретно в качестве выбирается следующая нумерация / 5, гл. Il3f]/i V(tt) есть -j , если п- четно, и - -в противном случае, /2= /, ,., .
В этом параграфе под слабой целочисленной ППА понимается слабая ППА., порожденная целочисленной ППА, а под ограниченной целочисленной ППА /по-зс /Х,/,,..} /Х /) ограниченная ППА, порожденная целочисленной ППА /при этом, как обычно, /ХІ модуль целого числа X /,
Наконец, при записи целочисленных функций прописные буквы /и,//,,., будем использовать в качестве функциональных символов, а переменные будем обозначать печатными буквами %Ц2,,.„; арифметические же функции будем обозначать как в 3,
В этом пункте мы покажем, что любую целочисленную прф /и только такую функцию/ можно построить в ограниченной цело-численной ППА из ноль-функции 0(к) /0(х)=о / , функции следования S(x) / (x)=x+i / , сложения Х+у , умножениях У , функция взятия целого числа с противоположным знаком -х , предиката строго меньше Xf и тождественных функций. Множество этих функций обозначим, как и во введении, через Є% .
Основной результат /теорема I/ будет получен из ряда лемм. +/ Определение представляющей функции см. в 4. ++/ Далее X - произвольное целое число. Лемма I. Пусть rfxir..,X ) - произвольная целочисленная функция, а У/2кг„ ...,-3) - арифметическая функция, представляющая ее. Тогда Доказательство очевидно.
Также очевидно, что в лемме I вместо арифметической функции J-fXi, .. , х,ъ) и нумерации t{hz) можно взять их целочисленные доопределения. Т.о., принимая обычное соглашение о включении множества натуральных чисел в множество целых 16?% для построения любой целочисленной прф /в ограниченной целочисленной ППА/ достаточно уметь строить, во-первых, целочисленное доопределение каждой арифметической прф, во-вторых, целочисленное доопределение нумерации tfx) и, в-третьих, обратную к ней функцию fX).
Это будет установлено в двух следующих леммах. Предварительно, чтобы не выходить из класса целочисленных функций, условимся, что понятие целочисленного предиката вводится аналогично случаю арифметических функций; также договоримся под доопределениями всюду далее понимать целочисленные доопределения.
Лемма 2. В ограниченной целочисленной ППА из множества функций 6Z строится доопределение каждой арифметической прф.
Доказательство Условимся далее через QnfXj-/ ), t% -обозначать такой целочисленный предикат, чтоОл(хг,..ухл)-U = c -O i iJJi для всех Хі,...,Хл. Упомянутые в лемме доопределения будем искать в классе таких целочисленных функций Р( 1г-, .) . что// ,...,)-0, как только Qjxbm/X (к) для всех 1} ...,..
Так как, в силу замечания 3.1, любую арифметическую прф можно построить из функций множества ( суперпозициями и операциями Л 0 , то доказательство проведем индукцией по чис-лу применений этих операций к функциям множества 61 . Начнем с базиса индукции. Очевидно, что доопределениями функций множества 6J » удовлетворяющими (х) , являются следующие целочисленные функции:
Полнота ППА в основных классах словарных вычисли мых функций
В этом параграфе будет дана алгебраическая характеристика в ППА классов словарных прф, орф и чрф. При этом понятие словарной прф, орф и чрф вводится аналогично случаю целочисленных и рациональных функций, надо только иметь в виду алфавитную нумерацию cL всех слов в произвольном фиксированном алфавите А {&ц-Арі,РЇ2, n00 061"1 » например в п. ІІ.іГ J. Как и для ранее рассмотренных классов функций, введем подходящие ППА словарных функций.
Под слабой словарной ППА договоримся понимать слабую ППА - 65 -порожденную словарной ППА, а под ограниченной словарной ППА -#г&Х ftVr ,..,Хп) ограниченную словарную ППА, где черезifx обозначена функция нахождения длины слова X .
Словарные функции будем записывать точно также как целочисленные и рациональные функции, а для арифметических сохраним прежнюю форму записи. Наконец, всюду далее под словами понимаются слова в алфавите А. « Полнота в классе словарных прф.
В этом пункте мы покажем, что любую словарную прф /и только такую функцию/ можно построить в ограниченной словарной ППА из функций множества 6у , состоящего из следующих функций: О/к), St O0j Ї-ЇР; SSfcyZ) тождественных функций и предиката Xf -4 Х% t Все эти функции были определены во введении.
Основной результат пункта будет получен из ряда лемм. В первых двух леммах покажем замкнутость класса словарных прф относительно операций ограниченной словарной ППА+ и примитивную рекурсивность всех функций множества б/j . При этом будут использоваться обозначения из 4.
Лемма I. Отображение 6 есть изоморфизм словарной ППА /слабой словарной ППА/ на арифметическую ППА /слабую арифметическую ППА/. Кроме того, Q есть гомоморфизм ограниченной словарной ППА на ограниченную арифметическую ППА.
Доказательство Первые два утверждения вытекают непосредственно из теоремы об изоморфизме ППА / 4/. Для доказательства третьего, в силу той же теоремы, достаточно проверить, что +/ Будет доказано более общее утверждение. для всех Но это неравенство вытекает из очевидного неравенства ot(fi) n для /г = %&,... /ведь с С - алфавитная нумерация/.U Отсюда и теорем S.I - 3,3 вытекает Следствие I. Класс словарных прф /чрф, орф/ замкнут относительно операций ограниченной словарной ППА /словарной ППА и слабой словарной ППА. соответственно/. Переходя к следующей лемме, договоримся под словарным предикатом понимать словарную функцию, значениями которой могут быть только пустое слово А. или буква df ; при этом /\_ интерпретируется как Л , a di - как // . Лемма 2. Все функции множества 6, примитивно рекурсивны. Доказательство Утверждение леммы для тождественных словарных функций тривиально, а примитивная рекурсивность функций 0(x)J S ifx)/ t= p и 6fX, 2) устанавливается в пп. II.I - 11,2 L 447. Поэтому остается рассмотреть предикат Ввиду следствия I, достаточно построить этот предикат в ограниченной словарной ППА из прф. Положим Pfy,Xz) fa Xi)4fXz A) / и FfaXz) P(xi/Xz) Xz (Xz) r#e ) - Функция предшествования, т.е. К(Л.)=А и К(хйі) = Х для любого слова х, С=ПЬ . Несложно проверить, что F(Xi; Х&)- Pfa/z) хя К(Хъ) » а та же то, ( ) =(х = F(xbкц) 4х,ФЦ\
В очевидных случаях не будем расписывать предикаты и функции с помощью суперпозиции.
Для завершения доказательства остается учесть примитивную рекурсивность предикатов Х/- , Х1 Ф Xz » Функции К(х) /ее легко построить словарной рекурсией из функции О(х) и селекторных функций; кроме того, класс словарных прф, в силу теоремы I из п.П.2Г 1 замкнут относительно словарной рекурсии/ и замкнутость класса примитивно рекурсивных предикатов относительно конъюнкции.D
Итак, ввиду лемм 1-2, остается показать, что любую словарную прф можно построить в ограниченной словарной ППА из функций множества 01 . Этому и будет посвящена оставшаяся часть пункта.
Мы хотим поступить аналогично случаю целочисленных и рациональных функций, однако, так как нельзя говорить о словарных расширениях арифметических функций, то необходимо кодировать арифметические функции словарными. Построим, следуя п. П.ЗГ 7, такое кодирование. Натуральное /г кодируем словом П=(24 (Ъ Оь /УО-Л./ , т.о., S) есть отображение множества натуральных чисел в множество слов в алфавите А. Это кодирование чисел естественно приводит к кодированию арифметических функций, отраженному в следующем определении.
Взаимная непроизводность основных операций ариф метической ППА и смежные вопросы
1. На основе понятия ППА, впервые введенного В.Н.Редько [/j, дана алгебраическая характеристика как традиционно рассматриваемых классов арифметических и словарных чрф, орф и прф, так и "нетрадиционных" классов вычислимых функций - классов целочисленных и рациональных чрф, орф и прф. При этом все классы орф и прф задаются единообразно с помощью специальных ограничений циклирования - так называемых слабых и ограниченных циклиро-ваний.
2. Установлена взаимная непроизводность суперпозиции, ветвления и циклирования в любой расширенной арифметической ШІА. Причем техника доказательства допускает перенос этого результата и на другие рассматривавшиеся ПЇЇА. Кроме того, показана непроизводность операций примитивной рекурсии и минимизации в снова же произвольной расширенной арифметической ППА.
3. Рассмотрены две подалгебры арифметической ППА: носитель первой состоит из всех арифметических частично рекурсивных функций и предикатов любой арности, а носитель второй -только из унарных арифметических частично рекурсивных функций и предикатов.
Для выписана система образующих; показано, что любую чрф можно построить из упомянутой выше системы образующих, ограничиваясь двойной глубиной циклирования /аналогично для предика тов/ и установлена континуальность семейства максимальных подалгебр.
Для алгебры $ и ее М і обеДнения построены системы образующих; показано, что для любых її Ї 2 и к 1 существует базис этой алгебры, состоящий в точности из /г примитивно рекурсивных функций и К примитивно рекурсивных предикатов, и не существует системы образующих, имеющей только одну функцию; установлено, что s имеет континуум максимальных подалгебр.
4. В приложении Д приведен разрешимый фрагмент элементарной теории класса всех так называемых примитивных программных структур /ППС/, состоящий в точности из всех универсальных формул соответствующего языка первой ступени.
Точные определения и доказательства помещены в приложении, здесь же отметим, что ППС строятся на основе ППА; при этом основные отличия следующие: во-первых, носитель ППС состоит только из унарных функций и предикатов, во-вторых, сигнатура ППС наряду со всеми операциями ППА содержит две ноль-арные операции /всюду истинный и всюду ложный унарный предикат/, а также бинарный предикат включения в смысле графиков.
Полученные результаты позволяют сделать такие выводы.
I. Аппарат ППА является удобным средством для задания самых различных классов вычислимых функций /по крайней мере, это было показано для двенадцати классов/. Очевидно, этим свойством ППА обладают ввиду независимости их основных операций от типов аргументов и значений функций, к которым /функциям/ эти операции применяются. Кроме того следует отметить, что наряду с мощностью операции ППА обладают и достаточной простотой.
2. Изучение ППА представляет и самостоятельный интерес; ППА имеют богатую содержательную теорию,- и в 4, гл. Ш и приложении Д сделаны только первые шаги в ее создании.
Оставшуюся часть заключения посвятим открытым вопросам, намечая иногда пути их решения.
Представляет несомненный интерес исследование полноты ППА в новых классах функций. Здесь в первую очередь хотелось бы назвать класс конструктивных функций конструктивных действительных чисел. При этом, однако, наверняка встретятся большие трудности идейного и технического плана.
Кроме того, учитывая особую роль унарных функций в теории алгоритмов, важно, с нашей точки зрения, иметь естественное описание в ППА классов арифметических унарных орф и прф; другими словами, построить аналоги известных алгебр Дж. и Р. Робинсон /заметим, что алгебру JS , рассматривавшуюся в п.10.2, можно считать аналогом алгебры Дж. Робинсон для чрф/. Представляется, что наибольшие трудности встретятся при описании класса орф; что же касается класса прф, то тут, возможно, будут полезны работы С.А.Березина [ 3 -ijno алгебраической характеристике классов одно- и двухместных арифметических прф.
