автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Функциональные системы рекурсивных функций и предикатов с сильными программными средствами замыкания

Р Г Б 0«

- 9 ОПТ Ш

На правах рукописи

СОЛОВЬЕВ Валерий Дмитриевич

ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ РЕКУРСИВНЫХ ФУНКЦИЙ И ПРЕДИКАТОВ С СИЛЬНЫМИ ПРОГРАММНЫМИ СРЕДСТВАМИ ЗАМЫКАНИЯ

05. 13. 17 - теоретические основы информатики

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

МОСКВА - 1995

Работа выполнена на кафедре теоретической кибернетики Казанского государственного университета им. .в. и. Ульянова-Ленин

Официальные оппоненты: доктор Физико-математических наук.

профессор Подловченко Р. И., доктор Физико-математических наук, профессор Добрипа В. П.. доктор Физико-математических наук, старший научный сотрудник Нарченков С. с.

Ведущая организация: Московский государственный университ«

1995г. вб

Зашита состоится зо*^ > 1995г. ви часов на заседай

диссертационного совета Д 002.32.Об вычислительного Центра ] по адресу: 117967, Носква. ГСП-1, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке Математиче кого Института РАН.

Автореферат разослан ЧС ОМ 1995г.

к.оЗ

Ученый секретарь диссертационного совета Шварткн с-м-

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Согласно 113- Ф. с. - это пара <£",Ä>, где У - множество Функций.(или Функций и предикатов), а Ä - множество операторов замыкания, позволяющих преобразовывать упорядоченные наборы элементов множества 7 снова в элементы !Г .

Бее Ф. с. рекурсивных Функций можно разделить на два типа: с алгебраическими операторами замыкания (это. так называемые, алгебры Робинсон) и с программистскими операторами замыкания. В последнем случае в качестве Ж используются различные классы схем програмн, а в качестве 7 - множества рекурсивных Функций и предикатов.

Начиная с первых работ по Ф. с. с программистскими операторами замыкания, в центре внимания оказалась проблема полнота. Проблема полноты в Ф. с. <У,Й> состоит в описании множества всех таких наборов элементов из Т , замыкание которых относительно # дает все множество ¥. Еще в 1967 г. Ершов A.n. и Ляпунов A.A. [2] включили проблему полноты в список важнейших нерешенных проблем теоретического программирования. Кудрявцевым В. Б. проблема полноты также отнесека

- 3 -

к основным проблемам теории ф. с. Непомнящий В. А. [3] сформулировал программу сопоставления различных классов схем программ по сложности критериев полноты в соответствующих Ф. с.

В последующие годы проблема полноты изучалась в работах Непомнящего В. А. , Голункова ю. в.. Савельева А. А. и других авторов для различных ф. с. рекурсивных Функций, но так и не была полностью решена. Оснозное внимание было уделено .Ф. с. со слабыми средствами замыгсания, такими, как системы алгоритмических алгебр Глущкова и стандартные схемы программ.

Проблема полноты имеет и другие аспекты: описание вычислимости средствами данного набора X. функций и предикатов и поиск наборов, порождающих данный класс вычислимых Функций.

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

Еше две области исследований имеют дело с объектами. Фактически очень близкими к ф. с. рекурсивных функций.

Одна из них - теория абстрактной вычислимости, целью которой является построение теории вычислимости над произвольными алгебраическими системами (их можно трактовать как абстрактные типы данных), возможно более близкой к вычислимости на Н. Если < > алгебраическая система с основным множеством А и сигнатурой оС , то вычислимыми на < А. X > считают Функции и предикаты из замыкания [¿£'1 сигнатуры X

относительно некоторого класса схем программ. При построе-

- 4 -

нии теории вычислимости таким способон Такер Дж. С41 высказал гипотезу, что на конечно пороченные алгебраические системы, порождающие элементы которых включены в сигнатуру X , можно полностью перенести классическую теорию алгоритмов. Таким образом, при счетном множестве эта теория имеет дело, как и теория Ф. с. , с замкнутыми классами Функций и предикатов.

Другая - это недавно возникшая теория моделей схем программ. Если классическая теория схем программ сравнивает классы схем программ по их транслируемое™ друг в друга, то есть по их поведению во всех интерпретациях, то теория моделей схем программ изучает поведение схем программ на отдельных интерпретациях -.моделях. Таким образом и здесь изучаются замкнутые множества для различных«^ и раз-

личных классов схем программ К.

Цель работы. Объектом исследований в диссертации являются Ф. с. рекурсивных Функций и предикатов с классами обогащенных схем программ в качестве средств замыкания. В качестве базовой выбрана Ф. с. одноместных общерекурсивных Функций и предикатов со схемами программ с массивами и равенством, как операторами замыкания. Целями работы являются:

1) решение проблемы полноты;

2) возможно более полное описание структуры замкнутых классов;

3) сравнение различных классов схем программ по свойствам соответствующих Ф. с. ;

1) разработка понятийного аппарата и общих методов

описания вычислимости в алгебраических системах.

- 5 -

Методы исследований. Для получения результатов, приведенных в диссертации, использован широкий спектр методов из теории рекурсивных Функций (построение "патологических" рекурсивно-перечислимых множеств, метод начальных сегментов, техника сводимости). логики, дискретной математики и программирования.

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

Научная новизна. Все результаты диссертации являются новыми. Впервые в систематической Форме изучены ф. с. с сильными программными средствами замыкания. Об-, наружена высокая степень регулярности структур замкнутых классов, что указывает на адекватность используемого аппарата. Предложен новый подход к проблеме полноты, состоящий в поиске критериев полноты, сформулированных на логическом языке, в результате чего решен ряд проблем, поставленных Ершовым А. П, и Ляпуновым А. А., Непомнящим В. А., Голунко-вым Ю. В., Такером Дж. Развит понятийный аппарат для описания замкнутых классов, а также техника нахождения базисов и критериев полноты з замкнутых классах, применимые для построения теории вычислимости в реальных алгебраических системах. Впервые показано наличие глубоких связей между классами рекурсивных функций и группами Бернсайда. разработан новый метод - анализ циклической структуры - изучения функций на N. Введен новый класс схем 'параллельных программ, необходимый для изучения вычислимости на частичных структурах. - б -

Основные результаты. выносимые на защиту. Получены критерии полноты для всех основных классов обогащенных схем программ, что практически завершает программу непомнящего В. А.

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

Для базовой Ф. с. :

- определена степень неразрешимости проблемы полноты;

- описаны все предполные классы;

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

- описаны все автоморфизмы упорядоченного по включению множества конечно-порожденных замкнутых классов;

- описаны все конечно-порожденные замкнутые классы, достижимые сверху за конечное число шагов;

- описаны покрытия атом<?в;

- доказано, что структура конечно-порожденных замкнутых классов, упорядоченная по включению, и структура Т-сте-пеней неразрешимости не элементарно эквивалентны.

Описаны все конечно-порожденные замкнутые классы Ф. с. с классом схем программ с косвенной адресацией (РАН-машины) в качестве операторов замыкания.

Описаны все замкнутые классы К-значных логик с дополнительной операцией разветвления по равенству.

Установлены связи вычислимости в частичных алгебраических системах посредством схем параллельных программ с поисковой вычислимостью Московакиса и с е-сводимостыо в теории алгоритмов. - 7 -

Теоретическая и практическая ценность. Полученные результаты позволяют по-новому взглянуть на рекурсивные Функции и расширяют существующие представления о вычислимости. Развитая в диссертации техника применима к описанию вычислимости в реальных алгебраических системах и абстрактных типах данных.

Разработанные методы могут быть применены в дальнейших исследованиях Ф. с. рекурсивных функций, к-значных логик и в теории моделей программ. Метод определения степени неразрешимости проблемы полноты был использован в ряде работ (например, в [51) для определения степеней неразрешимости проблемы полноты.алгебр Робинсон и других аналогичных проблем.

А п р обация работы и публикации. Результаты диссертации докладывались на семинарах: "Математические проблемы кибернетики" Яблонского с. в. , "Синтез управляющих систем" ЛУпанова О. Б., "Теория автоматов" Кудрявцева в. Б. , семинаре по дискретной математике в МГУ, Колмогоровском семинаре по математической логике, "Теория -нумераций" Гончарова С. С. в ИМ СО РАК, "Теория алгоритмов" Арсланова М. М., семинаре кафедры теоретической кибернетики Бухараева Р. г. , на всесоюзных конференциях по проблемам теоретической кибернетики, по математической логике, по прикладной логике, по системному и теоретическому программированию, на международной конференции "Fundamentals of Computation Theory, 1967".

все основные результаты диссертации опубликованы.в 26 печатных работах.

Структура работы. Диссертация состоит из введения, трех глав и списка использованной литературы (108 наименований). - 8 -

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава посвящена 4>. с. <7а, FDA=>, где % множество общерекурсивных функций (орф) и общерекурсивных предикатов (орп). FDA= - класс схем программ с массивами и равенством.

В первом параграфе доказан (теорема i. 1) критерий изоморфизма, характеризующий условия, при которых класс функций и предикатов, вычислимых в алгебраической системе средствами FDA_, изоморфен классу функяий и предикатов Т-сводя-щихся к некоторой степени неразрешимости.

Полученный результат позволяет дать положительный ответ на выше сФормулированную гипотезу Такера Дж. ■ при условии, что в алгебраической системе разрешима проблема тождества слов.

Другим следствием теоремы 1. 1 является критерий полноты конечного набора £ - i ft,.... fn. р4 ,... , рг(1! орФ и орп:

Следствие 1. 1. ¿f полол тогда и только тогда, когда

1) Vx, у Зт (t терм сигнатуры Х& т (х) - у ),

2 > 3 а 3 Ф ; Ф (х) бескванторная формула сигнатуры XU I - ) &Ф(а) & Vy i а 7<Р(у)).

Следствие 1. I обобщает критерий полноты Непомнящего В. А. , применимый только к наборам вида t f,:=0 ), на случай конечного числа функций и предикатов.

Критерий полноты позволяет дать ответ на вопрос Голун-

кова Ю. В. об определении степени неразрешимости проблемы

полноты. Заславским и. Д. было показано, что проблема полно- 9 - /

ты алгоритмически.неразрешима.

Теорема 1.2. Т-стецень проблемы полноты ( ее., так называемого, индексного множества ) есть О**.

Теорема 1. Ъ. Индексное множество проблемы полноты принадлежит уровню £&ПЛ3- (£аСЛ1г) иерархия Клини - Мос-товского.

Показано, что найденный критерий является, в некотором естественном смысле, простейшим возможным.

Критерий полноты может быть использован для выделения разрешимых случаев проблемы полноты.

Теорема 1.4. Существует алгоритм, который по любому конечному набору многочленов на Н ( отрицательные значения многочленов заменяются на О ) определяет, является ли он. полным или нет.

Во втором параграфе изучаются предполные классы Ф. с. < Т^ , ?ЬА->. где = ^ор^^ол. и ^оп соответственно множества одноместных орф и орп.

Применение критерия полноты позволяет дать следующую исчерпывающую классификацию предполных классов:

К1.1. Совокупность классов 01 таких, что

1) 3 а 3 Ф( Ф (х) бескванторная формула сигнатуры 011)1:) &Ф (а) & Уу í а 7ф(у)),

2) 3 х. у Ув е01 ( у i ей)).

К1. 2. Совокупность классов (Я таких, что

1) ЭаЭФ( Ф(х) бескванторная формула сигнатуры 0111 ( = ) & Ф (а) t ачФ(У)).

2) Ч х, у 3 8 е 01 ( у = к (х)),

3) ¿С^ШьХконечно & Ух.у ЗТсТтерм сигнатуры Х& & у = Т (х))).

- Ю -

кг. 1. Совокупность классов (JL таких, что

1) 3® ЗФ (Ф (х) бескванторная Формула сигнатуры CiU Ul-l & й) конечно & V а (( а — Ф (а)) & ( а 4 2) —

2) 3 ¿С ( &«£ конечно & Vx. у 3T(f терм сигнатуры & у = t (х))).

К2.г. Совокупность классов ОТ таких, что

1) тЗ®ЗФ(Ф(х) бескванторная Формула сигнатуры CTU U l = J & 2) конечно & V а( ( а £ 2) —- Ф (а)) & ( а 4 3) ~~~

7Ф(а))),

2) ЗХ (<5С£С7& ¿Сконечно & Vx, у т терм сигнатуры ¿f & & у = Т (х))).

В теоремах 1.5, 1.6, i.e. 1.9 приведены описания каждой из этих совокупностей. Решен вопрос о мощности каждой из них.

Следствие 1.4. К2. 1 счетна.

Остальные совокупности континуальны (следствие 1.2, теоремы 1. 7. 1. 10).

На основе полученных описан"й дано доказательство пред-полноты ряда конкретных классов.

Предложение 1. 10. Алгебра Фраттини (пересечение всех предполных классов) есть класс U0 = С TRUE. FALSE. ld(x) =

= X).

В третьем параграфе изучаются алгебраические свойства замкнутых классов Ф. с. < ?04, FDA _ >: существование в них автоморфизмов и конгруэндий. которые определяются стандартным способом.

Если оС - рекурсивная перестановка н, то отображение

•■р^ (f) = «С f of"1, (р) : РоС-1 является автоморфизмом

- li ~

(сохраняющим программные замыкания) Тд. if^ называется внутренним автоморфизмом.

Теорема 1. и. любой автоморфизм ?р является внутренним.

Техника доказательства теоремы 1. 11 применима и к описанию автоморфизмов и изоморфизмов замкнутых классов.

v

Предложение 1.12. Два предполных класса совокупности К1. 1 изоморфны тогда и только тогда, когда существует рекурсивная перестановка сС , индуцирующая изоморфизм.

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

Теорема 1.12. конечно-порожденный класс 0L является простым тогда и только тогда, когда 01 - и0 или 01 содержит функдии, отличные от id и tf d V ft. fг e Ot 3 h e Й ( h(d) f d & i 3 e € Oi ( ( g (dj) i f2( g(d)))K

Теорема 1. 12 позволяет описать все простые конечно-порожденные предполные классы. Это все предполные классы совокупности К2. 1. . а также все классы вида UA = ff | f(А)^ CAl U (конечно-порожденные и принадлежащие совокупности Kl. 1) при одноэлементном множестве А.

Во второй главе изучается структура, состоящая из всех конечно-порожденных замкнутых классов в Ф. с. < !S-q, FDA=>.

В первом параграфе описываются автоморфизмы этой структуры.

Обозначим через iS' множество замкнутых классов всюду определенных одноместных функций и предикатов для всех конечных наборов X Функций и предикатов на N (не только рекурсивных). & является верхней полурешеткой по вклю-

- 1.2 -

чению с начальным элементом и0 к без максимальных элементов. Элементы . расположенные мехду и0 и $о>~ это в точности замкнутые классы Ф. с. < У/.FDA_>. Для a ejf обозначим множество С xeS'ja&x) через iS'(^a).

Предложение 2. 1. структура S) т-степеней неразрешимости изоморфна 4L ( » .

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

Для расширения же Ж структуры 3) эта проблема решена следующим образом:

Теорема 2. 1. Автоморфизмы в точности суть внутренние.

Для доказательства теоремы 2, i разработан новый метод, основанный на детальном анализе циклической структуры Функций.

Следствие 2. 1. Автоморфизмы о?, отображающие в Т^г это в точности внутренние, индуцированные рекурсивными перестановками К.

В ходе доказательства теоремы 2. 1 получено описание атомов структуры У. т.е. таких классов 01. что V Й( 33 £ 01 — = U0 V 33 = 01 ).

Лемма 1. 01 атом ЙГ тогса и только тогда, когда

1) UL - [Fb Р 4 TRUE, i FALSE либо

2) UC = [f], где f функция такая, что Зп ( п простое число s.Vxif'Nx) = х 2Vi< n( 1 » 1 — fL (x> i x))).

функции из леммы l назовем циклическими.

Bo etopom параграфе изучаются замкнутые классы в ф с.

- 13 -

< Уо1. FDA„>. достижимые сверху за конечное число шагов.

Скажем ( аналогично [б] ). что замкнутый класс (71 достижим сверху за к шагов, если существует последовательность конечно-порожденных замкнутых классов 01^... & СК0 такая, что Oi0 - ff . = (Я и для всех 1 £ к - l 0Liti является предполным относительно Ot •.

Теоремы 2. 2 и 2. 3 дают полное описание (на языкэ теории категорий и групп перестановок) классов, достижимых сверху за конечное число шагов.

Приведем это описание для частного случая К = 1.

Следствие 2. 2. Конечно-порожденные предполные классы исчерпываются следующими двумя совокупностями:

I. ( f I f(A)£ A)U , где А рекурсивное множество, A i 6 , A i Н.

II. Пусть Т = ( Н )Г„ эффективное разбиение Н на рав-ноиощные множества, содержащие простое число элементов. G .- циклическая группа перестановок на Н и It\ Iz такие орФ, что V ( !,.< Mt) = Mitl& 12/Mltl- rtl/HiH) и I2/H0= id. Тогда определим совокупность классов (это в точности К2. 1) следующим образом:

I f| Vl 3eeG 3J ( f/Hi = lj.8 ii )) U t p| V iVx. у ( x, yfc H|. & P(X) —Р(У) H.

Для каждого из конечно-порожденных предполных классов указаны базисы и критерии полноты. Развитая техника применима к другим конечно-порожденным классам.

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

Теорема 2.4. Класс 01 достижим снизу за два шага (т.е.

- 14 -

является, так называемый, покрытием атома) тогда и только тогда, когда выполняется одно из следующих условий:

1) (К - С P. Q 1 ДЛЯ орп Р, Q i TRUE, t FALSE ИР i ^ Q.

2) (71 - t. f. P 1. где f - циклическая орФ, p t TRUE. t FALSE. hVx ( P(X)-~P(f (X)) ).

3) 01 - t f.p ], где f - циклическая орф, p i true,

t FALSE, и в каждом цикле ( ......fnl(x)l функции f предикат Р истинен ровно на одной элементе.

4) 01 = с f,g ], где f и s циклические орф и группа g перестановок Н. порождаемая Функциями frig полурегулярна к обладает тем свойством, что любая ее нетривиальная подгруппа. содержащая перестановку £. порождается ею.

Обозначим буквой V множество замкнутых классов и таких. что между U и и0 нет бесконечных цепей классов, описание покрытий атомов позволяет получить следующий результат: V не является верхней полурешеткой.

В доказательстве этого результата ключевую роль играет результат Ольшанского а.ю. о существовании групп Берн-сайда. все нетривиальные подгруппы которых имеют одинаковый

порядок.

Еше одним следствием теоремы 2. 4 является предложение 2.3 , означающее, что структуры S и Ф не элементарно эквивалентны.

Предложение 2. 3. Решетка ( о, а,1 1 с отношением порядка 0<а<! не вкладывается в в качестве начального сегмента.

третья глава посвяшена другим Ф. с. рекурсивных Функций.

В первом параграфе рассматрийаются Ф. с. < ^.К >, где

- 15 -

К следующие классы обогащенных схем программ: FDC= - счет-чиковые. FDS^ - с рекурсивными процедурами ( или со стеками ). FDAA= - с косвенной адресацией ( РАН-машины ).

Для всех них решена проблема полноты.

Теорема 3.1. [¿С ЭролА= = тогяа и только тогда, когда Vx. уЗтсг герм сигнатуры^ & *Т(х) = у ).

Условие полноты теоремы 3. Х- является, очевидно, необходимым для любых классов схем программ и, таким образом, слабейшим из возможных.

Предложение 3. 1.

1). С X JFj)3= = Р0 тогда и только тогда, когда

2). Для I X ]rDi;_ = тогда и только тогда, когда IX =

Критерий полноты для Ф. с. < Sj,. FDC_> получается добавлением к критерию полноты для <?0. FDA_> следующего условия С7]: V к -3 £ У at.....а^х Зт (т терм сигнатуры «£ & Т ( at.

.... at j = х — х может «ыть вычислен исходя из ( аА...., а ^ ) с использованием не более i ячеек памяти).

Сопоставление полученных критериев полноты позволяет установить общую закономерность - проблема полноты в Ф. с. решается тем легче, чем сильнее средства замыкания.

Для Ф. с. <ФВ\ FDAA_> описаны все конечно-порожденные замкнутые классы.

Теорема 3. 3. UL конечно-порожденный замкнутый класс в Ф. с. <%L. FDAA > тогда и только тогда, когда 9 п 3 ft,..., f„

ЗшЗр!.....pm (01 .= ! f | V х. у( у = f(x!—З£3к1.....Kt( у -

= ■ ■ • fir-(x)) I U f pIp/m является булевой комбинацией

предикатов p,.....РтП. где H = { xlVf^CKf(x) = x) i.

- 16 -

Во втором параграфе исследуются вопросы, возникающие при сопоставлении замкнутых классов в Ф. с. многоместных и одноместных орф и орп.

Определение 3. б. Для произвольного замкнутого класса 01 в Ф. с. <3J. FDA_> его основанием (обозначим его 011) назовен замкнутый класс 0LЛ ?0\

Степень зависимости класса от своего основания проясняется в следующих результатах.

Теорема 3.4. Если Я таково, что DI1- I f|f(A)£A с рекурсивным А ( *н. * ¿ ) • то DI имеет вид I f I V ... , хп€ 6А f( х1.....х^е А ШТ^и 01 = Е Ol^U tl^li^tn^n^eol.

Теорема 3. б. Если А сжато, то для UA = f fI V xt..... xn«A f(xt.....x„)fe A имеет место (-К»1:!//).

Показано, как развитая техника может быть применена к описанию вычислимости в полях.

Параграф 3 посвяшен случаю частично-рекурсивных функций ( чрФ ) и предикатов ( чрп ).

Обозначим через PFDA3 класс схем параллельных программ. получающийся из FDA- добавлением оператора AHI), распараллеливающего вычисления на две независимые ветви. Программа вычисляет некоторую функцию ( предикат ), если процесс вычислений на различных ветвях не может завершиться с разным результатом.

Показано ( предложение 3. 7 ), что класс PFDA_ является самым сильным (универсальным) среди всех классов, в некотором смысле разумно определенных схем программ.

При решении проблемы полноты для Ф. с. чрф и чрп с замыканием относительно. PFDA» получен критерий полноты, совпадающей по Формулировке с критерием полноты 1 главы 1.

- 17 -

Описана совокупность предполных классов, аналогичная совокупности Kl. 1 из второго параграфа главы 1. показано, что при использовании понятия эффективно-конечного порядка, описание совокупности Kl. 1 переносится на Ф. с. чрФ и чрп без изменений, в то время как использование понятийного аппарата теории рекурсивных функций не позволяет дать идентичного описания.

Также показано (теорема 3.10), что при некотором естественном определении представимости схенами программ Функционалов, класс функционалов, представииых схемами программ из PFDA совпадает с классом рекурсивных операторов.

В качестве следствия ■ получено описание, аналогичное найденному в [61, е-сводимости как сводимости посредством PFDA =

Изучена связь вычислимости в частичных алгебраических системах посредством схем из класса PFDA. с другими концепциями вычислимости. В частности, имеет место

Теорема 3. 9. Если для сигнатуры X алгебраической системы выполняется условие V х, у 3f (t-терм сигнатуры X & *Г( х ) = у ), то вычислимость посредством схем из PFDA-совпадает с поисковой вычислимость» Московакиса [91.

Полученные результаты показывают, что класс PFDA= для частичных Функций и предикатов играет ту же роль, что и класс F3A_ для всюду определенных.

В последнем четвертом параграфе изучается Ф. с. к-зна-чной логики с FDA = в качестве средств замыкания.

в связи с конечностью множества значений в к-значной

логике возможности класса FDAa сводятся к разветвлению по

равенству/ Обозначим через ( Р^. = ) Ф. с. к-значной логики

- 16 -

со следующей дополнительной возможностью порождения функций: h(x¿.... . хп): - if в4 (х^.....хп) '= Bjts^.....хп) then

f1(xi.....xft> else fa(xA.....хЛ).

Эта ф.с. изучалась в С101. где показано, что в ней существует лишь конечное число замкнутых классов.

Определение 3.13. Пусть F - оператор замыкания на множестве Е^ = ( 0.....К-1 1. Н - категория с множеством объектов { F(A) | AsE^a A t ф 5 и взаимно-однозначными отображениями в качестве морфизмов. Пару ¡F, Н) назовем согласованной.' если V A. B£E^Vo( Vjíj ■.... х„ ( Ж морФизм из F(A) в

F (В) & х4.....xneF(A)— o(/F( lx4.....хпП морФизм из Fit х4,

,...хп )) bf((o£(x1).....аС(Хп)П).

Теорема 3.11. Занкнутыми классами, в ( Pv = ) являются в точности множества Г f | V A,BVoí Vx4.....( f( x^.

.... xn) £ F(A) &cC морФизм из F(A) bF(B>— i( x4.....x„) -

«("■F(o( (xd).....(xn)») í. построенные по всевозможным согласованным парам (F,И).

Аналогичное описание дано для Ф. с. ( Р^. & ) с разветвлением по неравенству.

Литература

1. Кудрявцев В. Б. функциональные системы.-И. : Изд-во НГУ, 1982.

2. Epuob А. П. . Ляпунов А. А. о Формализации понятия програм-мы//Кибернетика. -1967. -№5. -С. 40 - 57.

3. Непомнящий В. А." Критерий алгоритмической полноты систем 'операций//Теория программирования, ч. 1. -Новосибирск.1972.

-С. 267 - 279.

4. TucKerJ. V. Computing in algebraic systems//Preprlnt series. -Osloirfatem. Inst. Univ. 1 Oslo,1978.

5. Голунков Ю. В. Степень неразрешимости проблемы полноты в , алгебрах рекурсивных Функдий//Нат. заметки. -1988. -Т. 44, №5. -С. 620-628.

6. Глушков В. Н. . Цейтлин Г. Е., юшенко Е. Л. Алгебра. Языки. Программирование. -Киев: Наукова Думка, 1974.

7. Kfoury A. J.. Urzyczyn P. Hecessary and sufflsient conditions for the universality of programming formalisms// Acta Informática. -1985. -V. 22. -P. 347 - 377.

8. He Evoy K. The structure of the enumeration degrees. -Ph. D. Thesis, Leeds Univ. -1984.

9. HoschovaKls Y. H. Abstract first order computabl1lty. I, II//Trans. Amer. Hath. Soc.-1969.-V. 138.-P. 427 - 504.

10. Тайманов В. А. О Функциональных системах к-значной логики с операциями замыкания программного типа//ДАН СССР. -1983.-Т. 268. №6.-С. 1307 - 1310.

ПУБЛИКАЦИИ ПО ТЕНЕ ДИССЕРТАЦИИ

1. Соловьев В. Д. Критерий полноты системы вычислимых функций и предикатов.//V Всесоюзн. конФ. по пробл. теор. кибернетики. Тезисы докл. -Новосибирск: ИМ СОАН СССР,1980.-С. 115.

2. Соловьев В. Д. Структура замкнутых классов вычислимых Функций и предикатов//Изв.вузов. Математика. -1982. -№12. -С. 51 - 56.

3. Соловьев В. Д. Степень неразрешимости проблемы полноты// VI Всесоюзн. конФ. по мат. логике. -Новосибирск: ИН СОАН СССР. 1982. -С. 172. - 20 -

4. соловьев В. Д. Структура предполных классов вычислимых функций и предикатов//IV Всесоюзн. симп. "Системное и те-орет. прогр. "-Кишинев: Штиинца. 1983. -С. 348 - 349.

5 Соловьев В. Д. Схемы программ и эффективные Функционалы конечных типов//Вероятностные методы и кибернетика. -1983.-вып. 19.-Казань': КГУ. -С. 129 - 132.

6. Соловьев В. Д. Подалгебры программной алгебры общерекурсивных функций и предикатов//У1II Всесоюзн. конф. по мат. логике. Тезисы докл. -м. : НГПИ. 1986. -С. 181.

7. Соловьев В. Д. Об одном классе параллельных схем программ //IV Всесоюзн. конФ. "Применение методов мат. логики". Тезисы докл. -Таллин: АН ЭССР.1986. -С.125 - 126.

8. Соловьев В. Д. Универсальные классы параллельных и недетерминированных схем программ,'/Вычислительные системы. -ВКП. 122. -Новосибирск: ИМ СОАН СССР, 1967. -С. 133 - 144.

9. Soloviev V. D. Nondeterministic finite algorithmic procedures as the models of abstract comPutability//'Lect. Kotes Comp. Sei.-1987.-V.276.-P. 409 - 411.

10. Соловьев В. Д. К-значные логики с разветвлениями - модель вычислимости схемами из КН0П-транзисторов//П Всесоюзн. конф. по прикл. логике. Тезисы докл. -Новосибирск: ИМ СОАН СССР,1988. -С.39 - 40.

11. Соловьев В. Д. Автоморфизмы структуры вычислительных тео-рий//1Х Всесоюзн. конФ. по мат. логике. Тезисы докл.-л. : Наука, 1988. -С. 153.

12. Соловьев В. Д. Полнота систем общерекурсивных Функций и предикатов. 1//'Известия вузов. Натем.-1989.-№8,-С. 56 - 63.

13. соловьев В. Д. Полнота систем общерекурсивных Функций к

предикатов. и//Известия вузов. Матем.-1989.-№9.-С. 60 - 66.

- 21 -

14. Соловьев В. Д. Замкнутые классы в К-значной логике с операцией разветвления по предикатам//Дискретная математика. -1990. -Т. 2, №4. -С. 19 - 25.

15. Соловьев В. Д. Алгебраические аспекты абстрактной теории вычислимости//Матем. вопросы кибер. -вьтп. 3. -м. : Наука, 1991.-С. 233 - 256.

16. Соловьев В.Д. Вычислительные теории над алгебрани//Неж-дун. конФ. по алгебре. Тезисы докл. -Новосибирск: ИМ СОАН СССР,1991.-С. 135 - 136.

17. Соловьев В. Д. Проблема полноты системы операций РАК-ма-шин//всесоюзн. конФ. "Прикладная логика". Тезисы. -Новосибирск:4 ИМ СО РАН.1991.

la. Soloviev V. D. Automorphisms of the program closed classes of functions and predicates structure//Recurslve Function Theory: newsletter. -1992. -№39. -P. 380.

19. soloviev V. D. Total recursive functions and predicates system comPleteness//Recursive Function Theory: Newsletter. -1992. -It39. -P. 361.

20. Соловьев В. Д. Программно замкнутые классы рекурсивных Функций и предикатов и группы Бернеайда//"Алгебра и анализ". -Усть-Кам. ГУ, 1993.-С.29 - 41.

21. Соловьев В. Д. Новое семейство предполных классов в Функциональных системах программного типа//Методы и системы технической диагностики. -Саратов: СГУ,1993. -С. 166 - 167.

22. Соловьев В. Д. Абстрактная теория вычислимости: программистский подход. -Казань: Казанский унив. , 1993.

23. Соловьев В. Д. Проблема полноты в алгебрах рекурсивных Функций с дополнительными средствами замыкания//Изв. вузов. Математика. -1993. -tf6. -С. 46 - 52.

- 22 -

24. соловьев В. Д. Структура программно замкнутая классов многоместных функций и предикатов//Изв. вузов. Математика. -1993. -№7. -С. 47 - 50.

25. Соловьев В. Д. Программно замкнутые классы обшерекурсив-ных функций и предикатов конечного ранга//Изв. вузов. Математика. -1993. -№9. -С. 51 - 63.

26. Соловьев В. Д. Вычислимость недетерминированными программами и поисковая вычислимость Московакиса//Мат. заметки. -1994. -Т. 56.1?1. -С. 149 - 152.

Сдано в набор 22.05.95 г. Подписано в печать 23.05.95 г. Форм.бум. 60 х 84 1/16. Печ.л.1,5. Тираж 100. Заказ 232.

Лаборатория оперативной полиграфии КГУ 420006 Казань, Ленина, 4/5