Введение к работе
АК1Хльность_темы. Теория конструктивных моделей интенсивно развивающееся направление математической логики, зародившаяся на стыке алгебры и теории алгоритмов в раоотах А.Фрейлиха, Дж.К. Шефердсона [23], М.О. Рабина [28] и А.И. Мальцева [9] в начале 60-х годов. В [9] обобщены разрозненные методы изучения конструктивных алгебраических объектов, намечены пути дальнейшего исследования и заложены основы новой теории.
Идея, положенная в основу понятия конструктивной модели, заключается в изучении объектов вместе с их вычислимыми нумерациями и восходит к работам К. Геделя и А.Н. Колмогорова. Использование понятия нумерации позволяет с единой точки зрения взглянуть на природу вычислимости алгебраических и теоретико-модельных конструкций и объединить методы теории алгоритмов с методами алгебры и теории моделей.
В последнее время наблюдается широкое проникновение в теорию конструктивных моделей проблем и идей, возникающих в Computer Science. Так, например, вычислимое семейство частично рекурсивных функций можно, согласно А.Н. Колмогорову (см. [13J), считать семантикой языка программирования низкого уровня. При этом номера функций соответствуют программам для вычисления функций. В » современных исследованиях по Computer Science, а также при создании языков программирования высокого уровня большая роль отводится понятию абстрактных типов данных. Одна из возможных семантик этого понятия может быть определена в терминах теории конструктивных моделей. Конструктивную модель (т.е. модель, все операции и предикаты которой рекурсивны относительно фиксированной нумерации) естественно рассматривать в качестве эффективной реализации некоторого абстрактного типа данных, а вычислимый класс конструктивных моделей - как эффективную реализацию базы данных.
При такой интерпретации автоустойчивым конструктивным моделям соответствуют такие типы данных, любые два эффективные представления которых эквивалентны, т.е.
автоматически транслируются друг в друга с точностью до изоморфизма.
Понятие алгебраически корректной алгоритмической массовой проблемы, согласно [13], определяется в рамках теории конструктивных моделей как отношение на модели, устойчивое относительно автоморфизмов. Согласно [29], это условие эквивалентно определимости отношения в языке ,, ,.,
ш ,ш
где С- сигнатура модели. Заметим, что относительно автоэквивалентных конструктивизации разрешима одни и те же алоритмические проблемы на данной модели.
Хорошо известное в теории конструктивных моделей понятие наследственно рекурсивно перечислимого отношения, эквивалентный аналог которого в терминах рекурсивных моделей исследован в [18], интерпретируется как алгоритмическая проблема, заданная на модели и имеющая алгоритм перечисления относительно любого эффективного представлений (конструктивизации) модели.
В настоящее время существует две школы, занимающиеся теорией конструктивных (рекурсивных) моделей. Первая, созданная А.И. Мальцевым и возглавляемая Ю.Л. Ершовым, включает С.С. Гончарова, М.Г. Перетятькина, Н.Г. Хисамиева, В.П. Добрицу, А.С. 'Морозова и других логиков. Вторая школа, возглавляемая А. Нероудом, включает Дж. Кроссли, К. Эша, Дж. Реммела, Дж. Найт, Дж. Чизхолма и других. Как первая так и вторая школа успешно работают в направлении, которое, следуя Дж. Кроссли [22], можно охарактеризовать как анализ того, какие алгоритмы неооходимо определить для той или иной теории или модели, чтобы гарантировать существование других алгоритмов или точно описать структуру модели.
В монографии Ю.Л. Ершова [8] подведены итоги первого этапа развития теории конструктивных моделей и сформулированы две основные проблемы: проблема существования конструктивизации у модели и конструктивной модели у теории и проблема числа неэквивалентных конструктивизации.
Со второй проблемой также тесно связаны проблемы существования и характеризации автоустойчивых моделей, моделей конечной и бесконечной алгоритмической размерности и
наследственно перечислимых отношений на конструктивных моделях. Эти проблемы изучались в работах С.С. Гончарова [2-71, А. Нероуда [18,27], К. Эша [15-19] и других авторов [20-22,25,30,33,34,42].
Тема диссертация связана с изучением условий эффективности выбора рекурсивних объектов в теории конструктивных моделей. Эффективный выбор соответствует возможности автоматического построения требуемого рекурсивного объекта: конструктивизаций, сводящей функции или перечислимого множества, что, в свою очередь, соответсвует возможности автоматического построения эффективной реализации базы данных по рассматриваемой на ней проблеме, автоматического построения трансляции с одного представления базы данных в другое и автоматического построения по представлению базы данных и проблеме соответствующего алгоритма перечисления решений данной проблемы.
Шль_диссертации. В диссертации разрабатывается новый подход к исследованию ряда классических проблем теории конструктивных моделей, связанный с изучением условий эффективности выбора рекурсивных объектов. Этот подход позволяет:
1) Показать, что в общем случае проблема описания
автоустойчивых моделей и моделей бесконечной алгоритмической
размерности и проблема описания наследственно перечислимых
отношений не имеют решения.
-
Сформулировать ряд дополнительных условий эффективности выбора подходящих рекурсивных объектов и решить вышеперечисленные проблемы при этих дополнительных условиях.
-
Заложить основы нового направления, связанного с выбором подходящих конструктивизаций модели по спецификациям проблем, заданных на модели.
Общая_мвтодика_исслеаований. В диссертации широко используются методы теории алгоритмов и рекурсивных функций, дескриптивной теории множеств и теории нумераций. В частности, используются метода приоритета с конечными и бесконечными нарушениями, аппарат топологии, теории игр и
теории категорий. ЫХ2ёя_ндвизна.
-
Выделение класса условий эффективного выбора и изучение моделей с точки зрения этих условий представляет собой новый нетрадиционный подход к теории конструктивных моделей, позволивший сформулировать ряд новых интересных проблем.
-
В диссертации разработаны принципиально новые методы построения конструктивизаций, удовлетворяющих требуемым свойствам, на базе метода приоритета с бесконечными нарушениями, аппарата размеченных деревьев и рекурсивных бесконечных формул.
-
Новые методы, разработанные автором, позволили решить ряд трудных проблем о моделях бесконечной алгоритмической размерности. В частности, решена известная проблема С.С. Гончарова о существовании модели бесконечной алгоритмической размерности, не имеющей вычислимых классов, содержащш бесконечно много неавтоэквивалентных конструктивизаций.
Все результаты диссертации являются новыми и обоснованы строгими доказательствами.
Практическая^^теоретическая^енность. Работа носит теоретический характер. Ее результаты и методы могут найти применение как в теории конструктивных моделей, так и в теории алгоритмов и рекурсивных функций. Полученные результаты дают решение ряда проблем из теории конструктивных моделей и могут быть использованы при чтении спецкурсов для студентов и аспирантов университетов.
Апробация. Результаты диссертации докладывались и анонсировались в разное время на логических семинарах ИМ СО РАН, НГУ, МГУ, КазГУ, на Всесоюзной конференции по логике (Алма-Ата, 1991), Межреспубликанской конференции по математической логике (Казань, 1992), Международной конференции по логике (Варна, 1990), Международном конгрессе по логике, методологии и философии науки (Уписала, 1991), Логическом Коллоквиуме Ассоциации Символической Логики (Весзпрем, 1992), Логическом Семестре (Варшава, 1991), Логическом Коллоквиуме АСЛ (Киль, 1993), 5-й Международной
Азиатской Логической конференции (Сингапур, 1993).
Публикации, основные результаты диссертации опубликованы и анонсированы-в работах автора [30-44].
Стру_кту_ра_диссертации. Диссертация состоит из введения, трех глав, приложения и списка литературы. Названия глав следующие: "Эффективно перечислимые отношения и эффективно автоустойчивые конструктивные и позитивные модели", "Вычислимые классы конструктивизаций моделей бесконечной алгоритмической размерности", "Эффективный выбор конструктивизаций и рекурсивная совместность проблем на конструктивных моделях". Объем диссертации - 180 страниц, список литературы включает 44 наименования.