Примитивные программные алгебры тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I. ОСНОВНЫЕ ПОНЯТИЯ.

§ I. Примитивные программные алгебры /ППА/.

§ 2. Примеры ППА.

ГЛАВА П. ПОЛНОТА ППА В ОСНОВНЫХ КЛАССАХ ВЫЧИСЛИМЫХ ФУНКЦИЙ

§ 3. Полнота ППА в основных классах арифметических вычислимых функций

§ 4. Слабые и ограниченные ППА. Изоморфизм ППА.

§ 5. Полнота ППА в основных классах целочисленных вычислимых функций.

§ 6. Полнота ППА в основных классах рациональных вычислимых функций.

§ 7. Полнота ППА в основных классах словарных вычислимых функций.

ГЛАВА Ш. АЛГЕБРАИЧЕСКИЕ СВОЙСТВА АРИФМЕТИЧЕСКОЙ ППА

§ 8. Расширенные ППА YL -арных функций и предикатов,

§ 9. Взаимная нецроизводность основных операций арифметической ППА и смежные вопросы.

§10. Некоторые подалгебры арифметической ППА.

Одна из актуальных задач современной теории программирования заключается в формализации семантики языков программирования. Из-за сложности этой задачи возникло несколько различных методов ее решения /см., например,[ 6^]/. Предлагаемая'работа основывается на композиционном подходе, заложенном в работах ВоН.Редько \5?-59 J.

В рамках композиционного метода было достигнуто не только существенное продвижение в формализации семантики языков программирования /см., например,[30, £5]/, но и реализован ряд систем программирования, например, система автоматизированного построения процессоров ДЕФИПС Г*г, /зЪ

Сущность композиционного подхода раскрывается в его принципах!^], среди которых мы отметим принцип функциональности и принцип композиционности.

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

По принципу композиционности для описания таких классов функций необходимо рассматривать алгебры функций, называемые в этом случае программными алгебрами /ПА/, замыкания в которых и будут задавать упомянутые классы функций.

В [60 ] была построена иерархия ПА, оправданность рассмотрения которой вытекает из большого разнообразия языков программирования, а, значит, и ассоциированных с ними классов функций.

Верхний уровень этой иерархии составляют фундаментальные ПА, нижний - примитивные ПА /ППА/, в качестве примера ПА промежуточного уровня укажем на элементарные ПА [// При этом выделение ППА связано с тезисом об их полноте в основных классах /эффективно/ вычислимых функций [6/ J.

Целью диссертационной работы как раз и является обоснование этого тезиса, т.е. вскрытие алгебраической структуры различных классов вычислимых функций на основе ППА; кроме того, будут исследованы и сами ППА.

Отметим, что в литературе неоднократно рассматривались различные алгебры вычислимых арифметических функций /т.е. функций натуральных аргументов и значений/; что же касается алгебр других классов функций, то здесь можно только отметить результаты А.И.Мальцева и И.Д.Заславского по характеристике класса словарных частично рекурсивных функций Г^, £<?1 /А.И.Мальцев, кроме того, рассмотрел алгебру словарных примитивно рекурсивных функций /п.П.зГ^]//t а также работы , в которых рассматривались алгебры унарных вычислимых функций в множестве кортежей, составленных из натуральных чисел.

Между тем, в литературе вводились вычислимые функции, отличные от "традиционных" вычислимых арифметических и словарных функций; например, рассматривались /как правило, без вскрытия алгебраической структуры соответствующих классов функций/ вычислимые функции в следующих областях: а/ множество кортежей, составленных из натуральных чисел

6/ множество кортежей, составленных из слов конечного алфавита в/ множество конечных графов /комплексов/Г3? >?б\\ г/ множество конструктивных действительных чиселf^ ]; д/ множество арифметических функций /гл. 10Г ^ J, § 9.8 [6/8 ]/, более того, можно рассматривать вычислимость на функционалах и более высоких типов /рекурсия в высших типах

Конечно, список примеров можно продолжить /см., например, [М ]/, еще больше примеров дают языки программирования.

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

Точное определение ППА будет приведено в гл. I, здесь же ограничимся неформальным обсуждением.

ППА имеет всего три параметрических операции: суперпозицию, ветвление и циклирование. Суперпозиция близка по существу к

Не путать с понятием целой рациональной функции в алгебре. одноименным операциям, рассматривавшимся в литературе; ветвление -аналог кусочного задания функций; циклирование - аналог простейшей циклической констукции языков программирования типа do ш(гс&, простота при этом заключается в том, что, грубо говоря, оператор тела цикла может менять значение только одной переменной. Принципиальная особенность этих операций состоит в их независимости от типа аргументов и значений функций, к которым они /операции/ при-+/ меняются. '

Формализмы, явно или неявно пригодные для вскрытия алгебраической структуры многих классов вычислимых функций, предлагались и ранее; для мотивировки введения ППА ниже будет дан их обзор. Подчеркнем, что речь будет идти о вскрытии структуры классов вычислимых функций, уже определенных тем или иным способом /по поводу таких способов см. уже упоминавшиеся обзоры А.П.Ершова/.

Первыми здесь следует назвать логические схемы программ А.А.Ляпунова [4/ ]и граф-схемы Л.А.КалужнинаГ^З ]. Так как в этих работах почти не рассматривались способы построения одних логических схем /граф-схем/ из других /за исключением операции подстановки граф-схемы I рода в граф-схему же/, то единственный способ извлечения операций состоит в связывании с каждой логической схемой /граф-схемой/ соответствующей операции. Но, в виду допущения логических схем и граф-схем любой сложностё^ сигнатура алгебр, построенных таким путем, будет очень сложной. Например, суперпозиция в обычном смысле обладает такой независимостью, в то время как примитивная рекурсия и минимизация /в классе арифметических функций/ - нет. Т.е., из-за неструктурированности этих объектов.

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

Переходим к операторным алгорифмам А.П.Ершова Отметим, что модели, по существу совпадающие с операторными алгорифмами, неоднократно вводились различными авторами Г^]; сюда следует отнести и различные "машинные" подходы [з^ у35 ^

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

Так, А.П.Ершов исследовал полноту операторных алгорифмов в классах арифметических и словарных вычислимых функций. Отметим, что при этом для задания вычислимых словарных функций в некотором алфавите приходится рассматривать операторные алгорифмы уже над этим алфавитом"1"/. вС^^ ]не рассматриваются способы построения одних алгорифмов из других /кроме композиции алгорифмов, аналогичной подстановке граф-схем Л.А.Калужнина/, поэтому отсюда извлечь нетривиальные операции в множестве функций не удается. Однако уже в работе И.Д.Заславского Г*2<Р ]тате операции имеются.

Центральное понятие этой работы - граф-схема с памятью.

Для задания этого класса использовались нормальные алгорифмы А.А.МарковаГ^], для которых, вообще говоря, необходимо расширять алфавит ]. B[/2<f , такое расширение алфавита не требуется.

Граф-схемы с памятью близки к граф-схемам Л.А.Калужнина и к операторным алгорифмам А.П.Ершова так называемого нулевого ранга /т.е., говоря содержательно, не меняющимся в процессе работы/.

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

Операции ППА близки к некоторым из операций нормального замыкания; в частности, аналогом циклирования ППА является операция повторения I рода функций /функторов по терминологии Г 2*1/ по предикату. Существенное отличие между этими операциями состоит в том, что при циклировании, грубо говоря, меняется значение только одной переменной, а при повторении I рода - в общем случае нескольких.

Отметим, что И.Д.Заславский установил полноту граф-схем с памятью в классах вычислимых арифметических и словарных функций.

Итак, отмеченные выше модели можно использовать для задания классов вычислимых или, говоря более точно, частично рекурсивных функций. Однако представляется невозможным их прямое применение для задания классов общерекурсивных функций. Что же касается субрекурсивных классов, то здесь следует упомянуть задание арифметических примитивно рекурсивных функций при помощи интерпретированных так называемых sltp -схем - частного случая граф-схем с памятью Г № j/см. также п.II.7 гл. ГУ п. г [ ] и

69 ]/+//. Особенность интерпретированных siep - схем состоит в том, что каждый их оператор цикла выполняется заранее известное конечное число раз, равное значению выделенной переменной перед выполнением этого оператора. Как видим, sitp - схемы ориентированы на арифметические функции. Забегая наперед, отметим, что при задании примитивно рекурсивных функций, не обязательно арифметических, с помощью ППА мы используем аналогичную идею.

Для классов унарных функций предлагались свои особые модели. Здесь сначала отметим системы алгоритмических алгебр /САА/ В.М.Глушкова 1, САА является двухосновной алгеброй, сигнатура которой состоит из семи операций над унарными операторами и условиями. Между ограничениями операций ППА на множество унарных функций и предикатов и операциями САА - умножением, j3 -дизъюнкцией, cL - итерацией, - существует тесная связь /отличия только в деталях/.

Переходя к полноте САА, укажем на результат Ю.В.Голункова по полноте САА в классе унарных вычислимых арифметических операторов и условий г ^ J.

Для характеристики классов унарных вычислимых функций также можно использовать операторные алгоритмы по терминологии п.14.3 книги А.И.Мальцева [М ]/в более ранней работе Я.М.Бард-зиняГ £ ]используется термин "М-операторы"/. Такие операторные алгоритмы близки к интерпретированным граф-схемам Л.А.Калужнина, а также к граф-схемам И.Д.Заславского, память которых состоит из одной переменной.

Более того, ,№]подтверждается известная иерархия

А.Гжегорчика[ М J.

Как и для операторных алгорифмов А.П.Ершова, в указанных работах не разрабатывались способы построения одних операторных алгоритмов из других, поэтому непосредственно извлечь интересные операции здесь не удается. Но можно учесть очевидную связь операторных алгоритмов с интерпретированными граф-схемами Л.А.Ка-лужнина и воспользоваться результатами работыТпо структуризации диаграмм. Однако на этом пути мы получим, по сути операции ПАА для унарного случая.

Отметим полноту операторных алгоритмов в классе унарных арифметических частично рекурсивных функций /теорема 2 п. 14.3 и теорема 3 п. 15.

Завершая обзор, укажем также на близость между операциями ППА и операциями над нормальными алгорифмами /гл. Ш §§ 5, бГ^ ]/, а также операциями, введенными в

Итак, операции ППА имеют ряд аналогов; конечно, точные взаимосвязи могут быть прослежены только после формального определения ППА, что и будет сделано в гл. I.

Перейдем к структуре и содержанию диссертационной работы. Она состоит из введения, трех глав, заключения, списка литературы и приложения. Главы состоят из параграфов, а параграфы г- из пунктов. Для параграфов принята сквозная нумерация, нумерация лемм и теорем в каждом параграфе своя. Для ссылок используется двойная нумерация, например, "лемма 2.1" - это первая лемма §2, а "п.3.3" - третий пункт §3. При ссылках внутри параграфа первый номер /номер параграфа/ будет опускаться.

ЗАКЛЮЧЕНИЕ .

В диссертационной работе получены следующие новые результаты.

1. На основе понятия ППА, впервые введенного В.Н.Редько \в{ ], дана алгебраическая характеристика как традиционно рассматриваемых классов арифметических и словарных чрф, орф и прф, так и "нетрадиционных" классов вычислимых функций - классов целочисленных и рациональных чрф, орф и прф. При этом все классы орф и прф задаются единообразно с помощью специальных ограничений циклирования - так называемых слабых и ограниченных цитирований.

2. Установлена взаимная непроизводность суперпозиции, ветвления и циклирования в любой расширенной арифметической ППА. Причем техника доказательства допускает перенос этого результата и на другие рассматривавшиеся ППА. Кроме того, показана непроизводность операций примитивной рекурсии и минимизации в снова же произвольной расширенной арифметической ППА.

3. Рассмотрены две подалгебры % > wv арифметической ППА: носитель первой состоит из всех арифметических частично рекурсивных функций и предикатов любой арности, а носитель второй -только из унарных арифметических частично рекурсивных функций и предикатов.

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

Для алгебры и ее | * J ~ обеднения построены системы образующих; показано, что для любых /г £ 2 и существует базис этой алгебры, состоящий в точности из /г примитивно рекурсивных функций и К примитивно рекурсивных предикатов, и не существует системы образующих, имеющей только одну функцию; установлено, что jiJ" ^ имеет континуум максимальных подалгебр.

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979. -536 с.

2. Бардзинь Я.М. Об одном классе машин Тьюринга /машины Минского/. Алгебра и логика, 1963, т.1, $ 6, с. 42 - 51.

3. Березин С.А. О порождении двухместных примитивно рекурсивных функций. Матем. исследования, 1972, т.7, вып.2, с.224-233.

4. Березин С.А. Об алгебре одноместных примитивно рекурсивных функций с операцией итерации общего вида. Кибернетика, 1976, № 3, с. 12 - 19.

5. Березин С.А. О максимальных подалгебрах алгебр рекурсивных функций. Кибернетика, 1978, № 6, с. 123 - 125,

6. Буй Д.Б., Воронов С,В., Мавлянов А.В., Самойленко А.Т. Проблемы реализации языковых процессоров в системе ДЕФИПС.

7. В кн.: Прикладное программирование. Киев: изд. ИК АН УССР, 1982, с. 9 14.

8. Буй Д.Б., Зубенко В.В. Разрешимые классы' схем программ над памятью. Докл. АН УССР, сер. А, 1982, № 7, с. 67 - 70.

9. Буй Д.Б. О проблеме пустоты для схем программ над памятью. -Докл. АН УССР, сер. А, 1983, № II, с. 72 74.

10. Буй Д.Б., Редько В.Н. Примитивные программные алгебры I. -Кибернетика, 1984, № 5, с.I 7.

11. Буй Д.Б., Редько В.Н. Примитивные программные алгебры целочисленных и словарных функций. Докл. АН УССР, сер. А, 1984, № 10, с. 69- 71.

12. Голунков Ю.В. О предполных классах алгоритмов, сохраняющих принадлежность множеству П. В кн.: Вероятностные методы и кибернетика. Вып. 17. Казань: изд. Казанского ун-та, 1980, с. 35 - 51.

13. Голунков Ю.В. О классах алгоритмов, сохраняющих отношения. -В кн.: Вероятностные методы и кибернетика. Вып. 18. Казань: изд. Казанского ун-та, 1982, с, 26 36.

14. Голунков Ю.В. Савельев А.А. Об алгоритмической полноте некоторых систем функций и предикатов. В кн.: Вероятностные ме-* v тоды и кибернетика. Вып. 20. Казань: изд. Казанского ун-та, 1984, с. 49 - 55.

15. Ершов А.П. Операторные алгорифмы. I /основные понятия/. В кн.: Проблемы кибернетики. Вып. 3. М.: Физматгиз, I960, с. 548.

16. Ершов А.П. Абстрактная вычислимость в алгебраических системах. В кн.: Алгоритмы в современной математике и ее приложениях. Часть П. Новосибирск: 'изд. ВЦ СО АН СССР, 1982,с. 194 223.

17. Ершов А.П. Вычислимость в произвольных областях и базисах. -В кн.: Семиотика и информатика. Вып. 19. М.: изд. ВИНИТИ, 1982, с. 3 58.

18. Ершов Ю.Л., Палютин Е.А. Математическая логика. М.: Наука, 1979. - 320 с.

19. Заславский И.Д. Граф-схемы с памятью. В кн.: Труды Матем. ин-та АН СССР, т. 72. М.: Наука, 1964, с. 99 - 192.

20. Захаров Д.А. Рекурсивные функции. Новосибирск: изд.Новосибирского ун-та, 1970.- 206 с.

21. Буй Д.Б., Мавлянов А.В. К теории программных алгебр. -Украинский матем. журнал, 1984, т. 36, № 6, с.761-764.

22. Буй Д.Б. Примитивные программные алгебры. В кн.: УП Всесоюзная конференция по математической логике. Тезисы докладов. Новосибирск: изд. Ин-та матем. СО АН СССР, 1984, е-. 23".

23. Волохов В.Н., Воронов С.В., Горбачик А.П., Карпенко И.В., Назаренко А.В. ДЕФИПС автоматизированная система построения языковых процессоров. - Управляющие системы и машины, 1984, № 3, с. 69 - 73.

24. Гжегорчик А. Некоторые классы рекурсивных функций. В кн.: Проблемы математической логики. Сложность алгоритмов и классы вычислимых функций. М.: Мир, 1970, с. 9 - 49.

25. Глушков В.М. Теория автоматов и формальные преобразования микропрограмм. Кибернетика, 1965, № 5, с. I - 10.

26. Глушков В.М., Цейтлин Г.Е., Ющенко E.I. Алгебра. Языки. Программирование. Киев: Наукова думка, 1978. - 318 с.

27. Голунков Ю.В. Алгоритмическая полнота и сложность микропрограмм. Кибернетика, 1977, № 3, с. I - 15.

28. Голунков Ю.В. К теории систем алгоритмических алгебр. -Докл. АН СССР, 1977, т. 232, № 4, с. 749 752.

29. Голунков Ю.В. О полноте операций в системах алгоритмических алгебр. В кн.: Алгоритмы и автоматы. Казань: изд. Казанского ун-та, 1978, с. II - 53.

30. Голунков Ю.В. О предполных классах алгоритмов, сохраняющих принадлежность множеству I. В кн.: Вероятностные методы и кибернетика. Вып. 16. Казань: изд. Казанского ун-та, 1980, с. 21 - 40.

31. SO. Зубенко В.В. Элементарные программные алгебры. Дао. . канд. физ.-мат. наук. Киев: Киевский ун-т, 1981. - 131 с.

32. Зуев М.Ф., Хвостанцев М.А. Об абстрактно-автоматной полноте в классе многоместных операторов. Кибернетика, 1981, № б, с. 13 - 16.

33. Зуев М.Ф. Вопросы конструктивной полноты в классе многоместных операторов и условий. В кн.: Труды Московского энергетического ин-та. Вып. 528. М.: изд. Московского энергетического ин-та, 1981, с. 83 - 88.

34. Калужнин Л. А. Об алгоритмизации математических задач. В кн.: Проблемы кибернетики. Вып. 2. М.: Физматгиз, 1959,с. 51 67.

35. Катленд Н. Вычислимость. Введение в теорию рекурсивных функции. М.: Мир, 1983. - 256 с.

36. Кафенгст Г. Абстрактная вычислительная машина с программным управлением. В кн.: Кибернетический сборник. Вып. 7. М.: ИЛ, 1963, с. 186 - 202.

37. Кекрис А., Московакис Я. Рекурсия в высших типах. В кн.: Справочная книга по математической логике. Часть Ш. М.: Наука, 1982, с. 166 - 223.

38. Колмогоров А.Н., Успенский В.А. К определению алгоритма. -Успехи матем. наук, 1958, т. 13, № 4, с. 3-28.

39. Котов В.Е. Введение в теорию схем программ. Новосибирск: Наука, 1978. - 256 с.

40. КУрош А.Г. Лекции по общей алгебре. М.: Наука, 1973. -400с.

41. Лингер Р., Мшите X., Уитт Б. Теория и практика структурного программирования. М.: Мир, 1982. - 406 с.

42. Ляпунов А. А, 0 логических схемах программ. В кн.: Проблемы кибернетики. Вып. I. М.: Физматгиз, 1958, с. 46 - 74.

43. Ляпунов А.А. К алгебраической трактовке программирования. -В кн.: Проблемы кибернетики. Выл. 8. М.: Физматгиз, 1962, с. 234 241.

44. Мальцев А.й. Конструктивные алгебры, I. Успехи матем. наук, 1961, т. 16, № 3, с. 3 - 60.

45. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1965. - 391 с.

46. Мальцев А.И. Итеративные алгебры и многообразия Поста. -Алгебра и логика, 1966, т. 5, № 2, с. 5 24.

47. Марков А.А. Теория алгорифмов. Труды Матем. ин-та АН СССР. Т.42. М.-Л.: изд. АН СССР, 1954. - 375 с.

48. Марков А.А. О конструктивных функциях. В кн.: Труды Матем. ин-та АН СССР. Т. 52. М.-Л.: изд. АН СССР, 1958, с.315-348.

49. Марченков С.С. Об одном методе построения максимальных подалгебр в алгебрах общерекурсивных функций. Алгебра и логика, 1978, т. 17, В 5, с. 581 - 595.

50. Марченков С.С. О квазипеановости рекурсивных функций. В кн.: Проблемы кибернетики. Вып. 35. М.: Наука, 1979, с.199 -204.

51. Марченков С.С. О мощности множества предполных классов в некоторых классах функций счетнозначной логики. В кн.: Проблемы кибернетики. Вып. 38. М.: Наука, 1981, с. 109 - 116.

52. Матиясевич Ю.В. Диафантовость перечислимых множеств. -Докл. АН СССР, 1970, т. 191, с. 279 282.

53. Минский М. Вычисления и автоматы. М.: Мир, 1971. - 364 с.

54. Михеев В.Л. Об одном классе алгебр примитивно рекурсивных функций. Матем. заметки, 1973, т. 14, № I, с. 143 - 156.

55. Нагорный Н.М. К усилению теоремы приведения теории нормальных алгоритмов. Докл. АН СССР, 1953, т. 90, № 3, с. 341 -342.

56. Никитченко Н.С. Композиционная семантика языков программирования. Программирование, 1982, 6, с. 9-18.

57. Еабин М.О. Разрешимость теорий второго порядка и автоматы над бесконечными деревьями. В кн.: Кибернетический сборник. Новая серия. Вып. 8. М.: Мир, 1971, с. 72 - 116.

58. Редько В.Н. Композиции программ и композиционное программирование. Программирование, 1978, № 5, с. 3-24.

59. Редько В.Н. Основания композиционного программирования. -Программирование, 1979, № 3, с. 3 13.

60. Редько В.Н. Семантические структуры программ. Программирование, 1981, I I, с. 3 - 19.

61. Редько В.Н. Императивные программные логики /основные результаты и открытые проблемы/ В кн.: Тезисы докладов П Всесоюзной конференции по автоматизации производства ППП и трансляторов. Таллин: изд. Таллинского политех, ин-та, 1983, с.109-III.

62. Редько В.Н. Универсальные программные логики и их применение. В кн.: Труды Всесоюзного симпозиума по теоретическому и системному программированию. Кишинев.: Штиинца, 1983, с.310-326.

63. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972, - 624 с.

64. Розикас М.Г. Алгебра многоместных примитивно рекурсивных функций. Уч. зап. Ивановского гос. пед. ин-та, 1972, № 117, с. 95 - III.- н?

65. Семантика языков программирования.Сб. статей.- М.: Мир, 1980.- 394 с.

66. Семенов А.Л. Некоторые алгоритмические проблемы для систем алгоритмических алгебр.- Докл. АН СССР,1978, т. 239,№ 5, с. 1063-1066.

67. Соколов В.А. 0 максимальных побалгебрах алгебры всех частично рекурсивных функций.- Кибернетика,1972, № Х,с. 70-73.

68. Феферман С. Числовые системы. Основания алгебры и анализа.-М.: Наука, 1971.- 440 с.

69. Янов Ю.И. О системах тождеств для алгебр.- В кн.: Проблемы кибернетики.Вып. 8. М.: Физматгиз,1962, с.76-90.69» Amihud A.,Choueka X. Loop-programs and Polinomially Computable Functions.- Intern. J. Computer Maths.,1981,v.9,N 3, p. 195-205.

70. Asser G. Berechenbare Graphenabbildungen.- In: Komplizier-theit von Lern-und Erkennungsprozessen. Jena:Friedrich-Schiller-- Universi tat, 1975»p. 7-17.

71. Bohm C.,Jacopini G, Flow Diagrams,Turing Machines and Languages with Only Two Formation Rules.- Comm. ACM, 1966,v.9 ,N 5, p.366-371.

72. Calude C.,Vieru V. An Iterative Noiraal Forn for Partial Recursive Functions.-' Foundations of Control Engineering,1981, v.6,IT 3,P.133-144.

73. Geimano G.,Maggiolo-Schettini A. Computable Stack Functions for Semantics of Stack Programs.- J. Сотр. Syst. Sci.,1979, v.19,N 2 ,p.133-144.

74. Germano G.,Maggiolo-Schettini A. Sequence Recursiveness without Cylindrification and Limited Register Machines.-Theor. Сотр. Sci ., 1981, v. 15,N 2,p.21>221.

75. Greibach S.A.Theory of Program Structures:Schemes,Semantics, Verification.- In: Lecture Notes in Computer Science.V.36. Berlin:Springer Verlag,1975.

76. Hare1 D.On Polk Theorems.- Comm. ACM,1980,v.23,N 7,p.379-389.77.<Jacopini G.,Kentrasti P.Punzioni ricorsive di sequenza.- Pub. blicazioni,serie III,no.104»I.А.С.,Roma, 1975•

77. SO.Meyer A.K.,Ritchie D.M.The Complexity of Loop Programs.- In: Proc. of the ACM 22nd National Conference.Washington D.C.: Thompson Book Co.,1967,p.465-469.

78. Reiser A.,Weihrauch K.Natural fiumberings and Generalized Com-putability.- Elektron. Informations Verarb. und Kybern.,1980, v.16,N 1-3,p.11-20.

79. Shepherdson J.C.,Sturgis H.E.Computability of Recursive Functions.» J. ACM,1963,v.10,N 2,p.217-255.