Оценка алгоритмической сложности классов вычислимых моделей

Академик А. И. Мальцев предложил использовать нумерации как базовую концепцию для изучения алгоритмических свойств алгебраических систем и их подмножеств, в частности таких классических систем, как группы, кольца и поля. Развивая это направление во взаимосвязи с общей теорией нумераций, С. С. Гончаров совместно с итальянским математиком А. Сорби предложили и разработали общий подход к понятию вычислимой нумерации, основанный на семантиках формальных языков. Изучение общих структурных свойств таких вычислимых нумераций на основе как соответствующих полурешеток Роджерса, так и в рамках локальных (внутренних) свойств таких нумераций через индексные множества в этих нумерациях является одной из важнейших исследовательских задач.

В рамках теории конструктивных моделей на сегодня разработаны различные подходы к исследованию алгоритмической и структурной сложности вычислимых моделей и отношений. Задача изучения структурных свойств вычислимых моделей и классов вычислимых моделей рассматривается как в рамках изучения сложности их ранга и формул Скотта, так и через индексные множества в универсальной нумерации вычислимых структур. Исследования в этом направлении были начаты в работах А. И. Мальцева, А. В. Кузнецова, Д. Макинси, К. Эша и А.Нероуда. Одним из продуктивных методов здесь является метод определимости в рекурсивном фрагменте языка бесконечных формул и задача изучения выразительных возможностей этого фрагмента языка в отношении описания свойств моделей. В этой связи актуальной является проблема нахождения формул и рангов Скотта для конкретных алгебраических структур и устойчивых относительно автоморфизмов отношений на них, исследование влияния на ранг Скотта константных и других естественных обогащений для алгебр, различных операторов над моделями, а также соотношений рангов и сложности структур для образов и прообразов. Этими проблемами занимались как зарубежные, так и российские математики, такие как Ершов, Гончаров, Каллибеков, Селиванов, Арсланов, Перетятькин, Добрица, Хисамиев и другие. Одно из направлений исследований связано с решением проблемы определимости и ее степени сложности в языке бесконечных формул. На этой основе могут быть получены верхние границы алгоритмической сложности, на основе теории вычислимых представлений алгебраических систем с различными свойствами, задаваемыми на декларативном языке спецификаций, — нижние оценки алгоритмической сложности рассматриваемой алгебраической проблемы.

К настоящему времени известно достаточно много результатов об индексных множествах моделей, классов моделей, теорий [1], [2], [3], [4], [5], [6], [7], [8], [9]. Большую роль индексные множества сыграли в общей теории вычислимости и вычислимых нумераций (кн. Ю. Л. Ершов. Теория нумераций [10]). Открытые проблемы этого направления привлекли специалистов и обсуждались на нескольких логических конференциях, в частности, приведены в работе Гончарова и Хусаинова [11], Гончарова и Найт [12].

Гончаров и Найт предложили [12] общие подходы для изучения структурных и алгоритмических свойств классов вычислимых моделей на основе исследования индексных множеств. Для многих классов индексное множество лежит на низком уровне гиперарифметической иерархии:

Предложение 0.1. Множество 1(К) является П^-множеством для следующих классов:

1. линейные порядки;

2. булевы алгебры;

3. абелевы р-группы;

4¦ модели эквивалентности;

5. векторные пространства над Q;

6. модели фиксированного вычислимого языка.

В работе [6] даны точные оценки для индексных множеств конструктивных моделей с заданными условиями автоэквивалентности рассматриваемых конструктивизаций. В работе [13] дана точная оценка индексного множества для локальных конусов. Ряд работ В. П. Добрицы посвящено изучению различных индексных множеств конструктивных моделей [6], [14], [15], [13], [16]. Для некоторых классов индексное множество гиперарифметично:

Предложение 0.2 (Клини, Спектор) Множество 1{К) является пол-ным для следующих классов:

1. полные порядки;

2. суператомные булевы алгебры;

3. редуцированные р-группы.

Для решения вопроса о существовании вычислимой классификации классов в [12] предложен подход оценки проблемы изоморфизма в терминах индексных множеств и приводятся доказательства оценок проблемы изоморфизма для некоторых важных классов.

Теорема 0.1. Множество Е (К) проблемы изоморфизма является полным для следующих классов К:

1. абелевы р-группы;

2. деревья;

3. булевы алгебры;

4¦ линейные порядки;

5. произвольные модели языка, содержащего по крайней мере один предикатный символ местности большей или равной 2.

Проблемы изоморфизма также исследуются в работах [1], [2] для вектор-пых пространств, алгебраических полей фиксированной характеристики, [17] для классов конструктивных /-алгебр, [18] для классов автоматных моделей.

Подход через индексные множества также позволяет оценить сложность семантических классов предложений, целая глава в монографии [19] посвящена оценкам алгоритмической сложности классов предложений, используемых в теории моделей и логике.

Настоящая работа посвящена исследованию вопроса о характеризации известных классов моделей через оценку сложности индексных множеств классов вычислимых моделей. С этой точки зрения можно рассмотреть классы специальных моделей (простые, однородные, насыщенные, универсальные), классы моделей с заданными свойствами теорий (теория допускает простую модель, счётная-категоричность теории, несчётная категоричность, Эренфойхтовость, разрешимость теории), классы моделей с фиксированными алгоритмическими свойствами (разрешимые модели, автоустойчивые, модели конечной (бесконечной) алгоритмической размерности, модели с вычислимым рангом Скотта, с невычислимым рангом Скотта,^{-разрешимые} счётно-категоричные модели, af-разрешимые простые модели). Решение вопроса об оценке сложности этих множеств находится в русле проблем, обсуждаемых в докладе Гончарова и Хусаинова [И], а именно с проблемами существования конструктивных моделей для определённых классов теорий, а также о максимальной сложности некоторых теорий, имеющих конструктивные модели.

11, Problems 3, 5, 11, Question 6].

Из перечисленных классов уже построены точные оценки для класса d-разрешимых моделей:

Теорема 0.2 ([9]) Для любой арифметической Тьюринговой степени d индексное множество всех d-разрешимых моделей нетривиальной сигнатуры viO 4 является т-полпым множеством.

Для класса^{-разрешимых} счётно-категоричных моделей:

Теорема 0.3 ([9]) Для любой арифметической Тьюринговой степени d индексное множество всех d-разрешимых счётно-категоричных моделей нетривиальной сигнатуры является т-полным Е3l, d множеством.

Для класса универсальных вычислимых моделей получена нижняя оценка:

Теорема 0.4 ([18]) Множество универсальных вычислимых моделей не менее чем Т,-полное.

Е.Б. Фокиной также была получена точная оценка индексного множества моделей, имеющих разрешимые теории:

Теорема 0.5 ([20]) Индексное мноэ/сество вычислимых моделей с разрешимом^ мыми теориями является т-полным Ъ2 множеством.

В последнее время в совместной работе российских и зарубежных специалистов был получен важный результат об индексных множествах структур высокого ранга Скотта:

Теорема 0.6 ([21]) Индексное множество класса вычислимых моделей:

1) имеющих невычислимый ранг Скотта является Т-полным;

2) имеющих ранг Скотта является И^-полным относительно системы обозначений Клини О;

3) имеющих ранг Скотта u>iK + 1 является Т^-полным относительно системы обозначений Клини О.

В данной работе применён подход понижения вычислительной сложности в теоретико-модельных конструкциях (подход Гончарова-Хусаинова на основе конструкции Маркера) [22] для получения нижних оценок алгоритмической сложности вычислимых представителей естественных классов моделей.

В работе использованы синтаксические характеризации классов моделей, обладающих о—категоричными теориями (Рылль-Нардзевский [23]), обладающих а^-категоричными теориями (Лахлан-Балдвин [24], Еримбетов [25]), современные результаты о синтаксической характеризации Эренфойхтовых теорий (Судоплатов, [26]). Для тех классов, для которых получены точные оценки, фактически подтверждается тезис выдвинутый в работе [3] о том, что точная оценка индексного множества даётся некоторым «оптимальным» описанием модели. В настоящей работе доказано, что упомянутые синтаксические характеризации обладают наименьшей возможной вычислительной сложностью, т. е. являются наилучшими синтаксической характеризациями с точки зрения вычислимости.

Заключение

.

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

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

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

Кроме того, для конечных моделей показана Е^-полнота соответствующего индексного множества.

В работе также была дана точная оценка сложности индексных множеств простых моделей,^{-разрешимых} простых моделей, моделей с Эренфойхтовы-ми теориями. Точность этих оценок говорит нам о том, что использованная синтаксическая характеризация этих классов является наилучшей вычислимой характеризацией, т. е. приведённые определения этих классов имеют наименьшую алгоритмическую сложность.

Были даны нижние и верхние оценки сложности индексных множеств вычислимых моделей с и^{iкатегоричными} теориями. Представлен универсальный способ получения нижних оценок для маркеровских свойств, т. е. таких теоретико-модельных свойств, которые сохраняются при маркеровских расширениях моделей. В качестве продолжения исследований в этом направлении можно рассматривать вопросы об оценке индексных множеств других классов моделей:

• однородные модели;

• насыщенные модели;

• допускающие разрешимое представление (допускающие п-разрешимое представление);

• автоустойчивые модели;

• модели бесконечной алгоритмической размерности;

• модели конечной алгоритмической размерности;

• с тотально-трансцендентной (No-стабильной) теорией;

• автоустойчивые относительно Да-изоморфизмов;