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

• Автор: Павловский, Евгений Николаевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Новосибирск
• Количество страниц: 95 с.

Содержание
Введение
1. Обозначения и терминология
2. Общая характеристика результатов работы
Глава 1. Конечные модели
1.1. Обозначения и предварительные результаты .*
1.2. Сигнатура с одной унарной операции
1.3. Сигнатура с несколькими унарными операциями
1.4. Случай произвольной сигнатуры
1.5. Индексное множество конечных моделей
Глава 2. Теоретико-модельные конструкции
2.1. Сведение произвольной сигнатуры к сигнатуре графов
2.2. Понижение алгоритмической сложности
2.3. Маркеровские расширения
2.4. Построение нижних оценок для маркеровских свойств
Глава 3. Индексные множества специальных классов моделей
3.1. Простые модели
Глава 4. Индексные множества классов моделей с заданными
свойствами теорий
4.1. Модели с и-категоричной теорией
4.2. Множество вычислимых ш-категоричных моделей
4.3. Эренфойхтовы теории
Литература

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

соотношений рангов и сложности структур для образов и прообразов. Этими проблемами занимались как зарубежные, так и российские математики, такие как Ершов, Гончаров, Каллибеков, Селиванов, Арсланов, Перетятькин, Добрица, Хисамиев и другие. Одно из направлений исследований связано с решением проблемы определимости и ее степени сложности в языке бесконечных формул. На этой основе могут быть получены верхние границы алгоритмической сложности, на основе теории вычислимых представлений алгебраических систем с различными свойствами, задаваемыми на декларативном языке спецификаций, — нижние оценки алгоритмической сложности рассматриваемой алгебраической проблемы.
К настоящему времени известно достаточно много результатов об индексных множествах моделей, классов моделей, теорий [1], [2], [3], [4], [5], [6], [7], [8], [9]. Большую роль индексные множества сыграли в общей теории вычислимости и вычислимых нумераций (кн. Ю.Л.Ершов. Теория нумераций [10]). Открытые проблемы этого направления привлекли специалистов и обсуждались на нескольких логических конференциях, в частности, приведены в работе Гончарова и Хусайнова [11], Гончарова и Найт [12].
Гончаров и Найт предложили [12] общие подходы для изучения структурных и алгоритмических свойств классов вычислимых моделей на основе исследования индексных множеств. Для многих классов индексное множество лежит на низком уровне гиперарифметической иерархии:
Предложение 0.1. Множество Т(К) является П-множеством для следующих классов:
1. линейные порядки;
2. булевы алгебры,;
3. абелевы р-группы;
6) |vi| 2, тогда vi — v[ v". Поэтому
н - H = [e((vw;)v2) 1%,*,)] - H;
(2) Пусть и = (ее), |r| 2. Тогда [ix] = a и v — v V2 Возможно три подслучая:
а) |v| 4, тогда v представимо, и [гг] = a[v] - искомое слово.
б) |v| = 3, т.е. [v] = Ь. Тогда [ад] = [ггг] = ab.
в) М = 2, т.е. [v] = а. Тогда [гг] — [ггг] = [(ее) (ее)] = аа.
(3) Пусть |гг| = 3, |г| 1. Тогда [u] = b и для г; возможно четыре подслучая:
а) |г| 4, тогда v представимо, и [гг] = Ь[г] - искомое слово.
б) |г[ = 3, т.е. [г] = Ь. Тогда [гг] = uv = bb.
в) |г| = 2, т.е. [г] = а. Тогда [гг] = [uv — [(е(ее))(ее)] = Ьа.
г) |г| = 1, т.е. v = е. Тогда
[гг] =- [uv] = [((ее)е)е] (Л=Л)Ь.
(4) Пусть |гг| 4, |r| > 1. Тогда и = щ гг2; где щ и щ - представимы. Для v возможно четыре подслучая:
а) |г| 4, тогда v представимо, и [гг] = [ггМ - искомое слово.
б) ]г| = 3. Тогда [гг] = [«i][]b.
в) ]г| = 2. Тогда [гг] = i][tt2]a.
г) |г| = 1. Поскольку |ui| + |гх21 4, то либо и — гг) гг", либо
U2 = г/-2 гг'2 В первом варианте получаем
[гг] = [((гг) гг") гг2)е] [(гг) гг") гг2] = [гг] - представимо.