Введение к работе
Актуальность темы. Концепция алгоритма является одной из центральных в информатике и изучается с разных точек зрения различными частными теориями. Так, теория рекурсивных функций - устоявшийся раздел математической логики - изучает функции с точки зрения существования или несушествсвания алгоритмов, их вычисляющих. Теория Функциональных систем (Ф. с. ) рекурсивных функций изучает классы функций более узкие, чем класс всех рекурсивных Функций, а также способы задания алгоритмов.
Согласно И), ф. с. - это пара <Т,Л>, где У - множество функций.(или Функций и предикатов), а Л - множество операторов замыкания, позволяющих преобразовывать упорядоченные наборы элементов множества У снова в элементы Т .
Бее Ф. с. рекурсивных Функций можно разделить на два типа: с алгебраическими операторами замыкания (это. так называемые, алгебры Робинсон) и с программистскими операторами замыкания. В последнем случае в качестве Ж используются различные классы схем програми, а в качестве Т - множества рекурсивных Функций и предикатов.
Начиная с первых работ по Ф. с. с программистскими операторами замыкания, в центре внимания оказалась проблема полноты. Проблема полноты в Ф. с. <У,Й> состоит в описании множества всех таких наборов элементов из Т , замыкание которых относительно Зі. дает все множество (Г. Еще в 1967 г. Ергаов А. П. и Ляпунов А. А. [21 включили проблему полноты в список важнейших нерешенных проблем теоретического программирования. Кудрявцевым В. Б. проблема полноты также отнесека
к основным проблемам теории ф. с. Непомнящий В. А. [3] сформулировал программу сопоставления различных классов схем программ по сложности критериев полноты в соответствующих Ф. с.
В последующие годы проблема полноты изучалась в работах Непомнящего В. А. , Голункова ю. в.. Савельева А. А. и других авторов для различных ф. с. рекурсивных Функций, но так и не была полностью решена. Оснозное внимание было уделено .Ф. с. со слабыми средствами замыкания, такими, как системы алгоритмических алгебр Глущкова и стандартные схемы программ.
Проблема полноты имеет и другие аспекты: описание вычислимости средствами данного набора X. функций и предикатов и поиск наборов, порождающих данный класс вычислимых Функций.
Важным направлением в изучении Ф. с. рекурсивных функций является описание структуры замкнутых классов и установление их алгебраических свойств, таких как наличие конгруэнции, автоморфизмов.
Еше две области исследований имеют дело с объектами. Фактически очень близкими к ф. с. рекурсивных функций.
Одна из них - теория абстрактной вычислимости, целью которой является построение теории вычислимости над ПРОИЗВОЛЬНЫМИ алгебраическими системами (их можно чтзактовать как абстрактные типы данных), возможно более близкой к вычислимости на Н. Если < К,Х > алгебраическая система с основным множеством А и сигнатурой оС , то вычислимыми на < А. X > считают Функции и предикаты из замыкания [\ сигнатуры X
относительно некоторого класса схем программ. При построе-
ний теории вычислимости таким способом Такер Дж. [41 высказал гипотезу, что на конечно порожденные алгебраические системы, порождающие элементы которых включены в сигнатуру X , можно полностью перенести классическую теорию алгоритмов. Таким образом, при счетном множестве эта теория имеет дело, как и теория Ф. с. , с замкнутыми классами Функций и предикатов.
Другая - это недавно возникшая теория моделей схем программ. Если классическая теория схем программ сравнивает классы схем программ по их транслируемости друг в друга, то есть по их поведению во всех интерпретациях, то теория неделей схем программ изучает поведение схем программ на отдельных интерпретациях -.моделях. Таким образом и здесь изучаются замкнутые множества 1\- для различных of и различных классов схем программ К.
Цель работы. Объектом исследований в диссертации являются Ф. с. рекурсивных Функций и предикатов с классами обогащенных схем программ в качестве средств замыкания. В качестве базовой выбрана Ф. с. одноместных общерекурсивных Функций и предикатов со схемами программ с массивами и равенством, как операторами замыкания. Целями работы являются:
-
решение проблемы полноты;
-
возможно более полное описание структуры замкнутых классов;
-
сравнение различных классов схем программ по свойствам соответствующих Ф. с. ;
-
разработка понятийного аппарата и общих методов
описания вычислимости в алгебраических системах.
Методы исследований. Для получения результатов, приведенных в диссертации, использован широкий спектр методов из теории рекурсивных Функций (построение "патологических" рекурсивно-перечислимых множеств, метод начальных сегментов, техника сводимости). логики, дискретной математики и программирования.
Разработан новый метод описания автоморфизмов структуры замкнутых классов Ф. с., состоящий в анализе циклической структуры Функций.
Научная новизна. Все результаты диссер
тации являются новыми. Впервые в систематической Форме изу
чены ф. с. с сильными программными средствами замыкания. Об-,
наружена высокая степень регулярности структур замкнутых
классов, что указывает на адекватность используемого аппа
рата. Предложен новый подход к проблеме полноты, состоящий
в поиске критериев полноты, сформулированных на логическом
языке, в результате чего решен ряд проблем, поставленных
Ершовым А. П. и Ляпуновым А. А., Непомнящим В. А., Голунко-
вым Ю. В.. Такером Дж. Развит понятийный аппарат для описа
ния замкнутых классов, а также техника нахождения базисов
и критериев полноты з замкнутых классах, применимые для по
строения теории вычислимости в реальных алгебраических си
стемах. Впервые показано наличие глубоких связей между
классами рекурсивных функций и группами Бернсайда. Разрабо
тан новый метод - анализ циклической структуры - изучения
функций на Н. Введен новый класс схем 'параллельных программ,
необходимый для изучения вычислимости на частичных структу
рах. - б -
Основные результаты. выносимые на зашиту. Получены критерии полноты для всех основных классов обогащенных схем программ, что практически завершает программу непомнящего В. А.
Доказана гипотеза Такера Дж. о вычислимости в конечно-порожденных алгебраических системах.
Для базовой Ф. с. :
определена степень неразрешимости проблемы полноты;
описаны все предполные классы;
описаны все конечно-порожденные простые замкнутые классы;
описаны все автоморфизмы упорядоченного по включению множества конечно-порожденных замкнутых классов;
описаны все конечно-порожденные замкнутые классы, достижимые сверху за конечное число шагов;
описаны покрытия атомов;
доказано, что структура конечно-порожденных замкнутых классов, упорядоченная по включению, и структура Т-сте-пеней неразрешимости не элементарно эквивалентны.
Описаны все конечно-порожденные замкнутые классы Ф. с. с классом схем программ с косвенной адресацией (РАН-машины) в качестве операторов замыкания.
Описаны все замкнутые классы К-значных логик с дополнительной операцией разветвления по равенству.
Установлены связи вычислимости в частичных алгебраи
ческих системах посредством схем параллельных программ с
поисковой вычислимостью Носковакиса и с е-сводимостью в те
ории алгоритмов. ,
теоретическая и практическая ценность. Полученные результаты позволяют по-новому взглянуть на рекурсивные Функции и расширяют существующие представления о вычислимости. Развитая в диссертации техника применима к описанию вычислимости в реальных алгебраических системах и абстрактных типах данных.
Разработанные методы могут быть применены в дальнейших исследованиях Ф. с. рекурсивных функций, к-значных логик и в теории моделей программ. Метод определения степени неразрешимости проблемы полноты был использован в ряде работ (например, в [51) для определения степеней неразрешимости проблемы полноты.алгебр Робинсон и других аналогичных проблем.
А п р обация работы и публикации. Результаты диссертации докладывались на семинарах: "Математические проблемы кибернетики" Яблонского С в. . "Синтез управляющих систем" ЛУпанова О. Б., "Теория автоматов" Кудрявцева в. В. , семинаре по дискретной математике в ИГУ, Колмогоровском семинаре по математической логике. "Теория -нумераций" Гончарова С. С. в ИМ СО РАК, "Теория алгоритмов" Арсланова М. М., семинаре кафедры теоретической кибернетики Бухараева Р. г. , на всесоюзных конференциях по проблемам теоретической кибернетики, по математической логике, по прикладной логике, по системному и теоретическому программированию, на международной конференции "Fundamentals of Computation Theory, 1967".
все основные результаты диссертации опубликованы.в 26 печатных работах.
Структура работы. Диссертация состоит из введения, трех глав и списка использованной литературы (108 наименований). - 8 -
