О тьюринговой сложности классов моделей и теорий

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

Оглавление
Введение
1 Методы преобразования моделей
1.1 Метод понижения сложности
1.2 Метод сведения сигнатур
1.3 Функторы для сведения к сигнатуре графов
2 Сложность теорий с вычислимыми моделями
2.1 Сложность несчетно категоричных теорий с вычислимыми
моделями
2.2 Сложность счетно-категоричных теорий с вычислимыми моделями
3 Индексные множества
3.1 Разрешимые модели
3.2 Разрешимые счетно-категоричные модели
3.3 Модели с разрешимой теорией
3.4 Приложения к известным классам
4 Алгоритмические свойства унаров
4.1 Функтор, сводящий графы к моделям сигнатуры с двумя одноместными функциональными символами
4.2 Алгоритмические свойства моделей сигнатуры с двумя одноместными функциональными символами
Литература

ВВЕДЕНИЕ
Формализация понятия алгоритма и исследование феномена вычислимости породили интерес к изучению эффективных математических объектов, следствием чего стало развитие такого направления теории вычислимости, как теория вычислимых моделей. Основы теории вычислимых моделей были заложены в 50-е годы в работах А. И. Мальцева [25], Р. Во-ота [64], А. Фролиха и Дж. Шефердсона [42], О. Рабина [60]. В работе
А. И. Мальцева [24] были намечены основные направления развития этой теории. Существенный вклад в развитие теории вычислимых моделей был сделан Ю. Ершовым. Предложенное им понятие сильно конструктивной модели [17] было базисным для развития теории разрешимых моделей, которая явилась синтезом абстрактной теории моделей и теории вычислимости. Понятие сильно конструктивной модели позволило изучать алгоритмические свойства моделей разрешимых элементарных теорий. Основные направления исследований в теории вычислимых моделей в мире были отражены в двухтомном издании "Handbook of Recursive Mathematics" [41] под редакцией Ю. JI. Ершова, С. С. Гончарова, А. Нсроуда, Дж. Ремме-ла. Развитие теории вычислимых моделей в России нашло отражение в монографии Ю. JI. Ершова и С. С. Гончарова [10]. Наиболее актуальные проблемы и современные пути развития теории вычислимых моделей были отражены в работах С. С. Гончарова и Б. Хусайнова [43] и С. С. Гончарова [40].
Понятие вычислимой (конструктивной) модели было введено в связи с изучением алгоритмических проблем как в математической логике, так и в алгебре. Основной задачей теории вычислимых моделей является

выявление и описание взаимосвязей между алгебраическими, теоретикомодельными и алгоритмическими свойствами моделей. Одно из важных направлений теории вычислимых моделей связано с изучением условий существования вычислимых моделей с заданными элементарными свойствами. Другой вопрос, связанный с первым, — найти связи между алгоритмической сложностью моделей и различными теоретико-модельными свойствами их теорий. Это направление исследований является актуальным и привлекает внимание многих специалистов, таких как Ю. Ершов, С. Гончаров, А. Морозов, В. Добрица, Дж. Найт, С. Лемпп, А. Нис, В. Ха-ризанова, Б. Хусаинов и другие.
Введем основные определения. Зафиксируем вычислимую геделев-скую нумерацию сигнатуры о. Считаем, что носители моделей содержатся в и>, которое мы рассматриваем как вычислимое множество констант.
Определение 0.0.1. Модель А сигнатуры а вычислима, если ее основное множество вычислимо, базисные операции и предикаты равномерно вычислимы.
Мы отождествляем формулы с их геделевскими номерами. Тогда вычислимость модели эквивалентна условию, что атомная диаграмма Т>{Л) этой модели вычислима, где Т>{А) = атомная формула или
отрицание атомной формулы без свободных переменных сигнатуры сгд и А |= Определение 0,0.2. Модель А сигнатуры а разрешима, если вычислима ее полная диаграмма Т>С(А) = предложение сигнатуры а а и
А 1=
Доказательство. Пусть <т0 = {Ро°> Г'» > Р) и ПУСТЬ Л — модель сигнатуры а о с основным множеством |Л|. Рассмотрим предикатный символ к
Р местности п = 2пг и сигнатуру иI = (Рп).

Строим модель Л' сигнатуры од следующим образом. В качестве основного множества рассматриваем множество Ж = {оо}и|Л|. Здесь предполагаем, что оо ф |Л|. На Л! определяем Р следующим образом. Полагаем (х
1. х — х2 — ... = хп = оо;
2. Существует г < к и г/1,, уп., такие что х+т; = для всех у, таких ЧТО 1 < у < Пг И Л [= Рг(у1, . , Уп,): и ту = ос для всех j, что

1 < у < гПг или тг- + п,- + 1 < у < п. Здесь т0 = 0 и тг

г > 1.
Проверяем свойства С УП.
1. Полагаем ф(х) = Р{х
2. Отношение 11{х) определимо формулой -пР(х
3. Отношения Яфжъ Лп.) определимы формулами
Р(оо
4 ' V— 4 V "
ТП{ ТЫ П-ТПг+1
4. Для любой копии А модели Л соответствующая копия А' с(А)-вычислима по определению;
5. По определению;
6. Пусть к : и(Л;) —V(А') такова, что

Рг{У> 1 Уп,) 4=4- Рф/фуД, . , /ф?/п;))